code-hunt

Little Stuart has reached the final level of 'Code Hunt', the annual treasure hunt organised by HackerEarth. Now for the final level, Little Stuart has to choose a door from infinite number of doors numbered from 1 to infinity. Out of these only one door contains the grand prize. The clue for finding the correct door is as follows 

Your task is to help Little Stuart find the correct door, so that he can win.
DoorNumber=0

for (i=0;i<ArraySize-1;i++)

  for(j=i+1;j<ArraySize;j++)

       if(GCD(a[i],a[j])==a[j])

             if(GCD(2^a[i]-1,2^a[j]-1)==2^a[j]-1)

                  DoorNumber=DoorNumber+1;
             else 
                  DoorNumber=DoorNumber-GCD(2^a[i]-1,2^a[j]-1);

print DoorNumber

NOTE:Here "^" is not xor operator , it is meant for power here.
Input:
First line contains a integer "T" ,number of test cases .Each test case contain two lines , first line contains value of ArraySize (size of array) and second line contain values of array elements.

Output:
For each test case print the value of DoorNumber.

Constraints:
1 ≤ T ≤ 20
1 ≤ ArraySize ≤ 10^5
1 ≤ a[i] ≤ 100

SAMPLE INPUT
2
3
10 2 3
2
3 5

SAMPLE OUTPUT
1
0

Source: hackerearth | Difficulty: MEDIUM
Tags: Number theory


Solutions:
t=eval(input())
l1=[]
while(t>0):
	size=eval(input())
	a=[]
	cnt=[0]*105
	count=[0]*105
	Count=0
	a=list(map(int,input().split()))
	for i in range(0,size):
			cnt[a[i]]+=1
	
	for i in range(0,size):
			count[a[i]]+=1
			j=1
			while(j*j<=a[i]):
					num=a[i]
					if(num%j==0):
							divisor1=j
							divisor2=num/j
							if(divisor1==divisor2):
									Count+=(cnt[divisor1]-count[divisor1])
							else:
									Count+=(cnt[divisor1]-count[divisor1])
									Count+=(cnt[divisor2]-count[divisor2])
					j+=1
	l1.append(Count)	
	t-=1

for i in l1:
	print(i)


t = int(input())
for k in range(t):
	door = 0
	arrsz = int(input())
	arr = [int(x) for x in input().split()]
	cnt = {}
	for i in range(1,101):
		cnt[i] = 0
	cnt[arr[0]] = 1
	currmx = arr[0]
	for i in range(1,arrsz):
		m = 0
		n = 1
		while(arr[i]*n <= currmx):
			m = m + cnt[arr[i]*n]
			n = n + 1
		door = door + m
		cnt[arr[i]] = cnt[arr[i]] + 1
		if arr[i] > currmx:
			currmx = arr[i]
	print(door)