# PROBLEM LINK:

**Author:** Md Shahid

**Tester:** Soham Chakrabarti

**Editorialist:** Md Shahid

# DIFFICULTY:

Easy

# PREREQUISITES:

Math, GCD and LCM

# PROBLEM:

Given an array **A**, you need to calculate number of pairs which satisfied the following conditions :

- LCM(A_i, A_j) = 2*GCD(A_i, A_j), where 1\leq i \leq N and 1\leq j \leq N
- (A_i, A_j) = (A_j, A_i)

# QUICK EXPLANATION:

If you observe carefully then you will notice that, LCM(A_i, A_j) = 2*GCD(A_i, A_j) is only possible when A_i = 2*A_j or A_j = 2*A_i . As second condition says that (A_i, A_j) = (A_j, A_i) which means there will be only one pair possible when A_i = 2*A_j or A_j = 2*A_i.

# EXPLANATION:

The mathematical explanation is as follows :

=>LCM(A_i, A_j) = 2*GCD(A_i, A_j)---(1)

As LCM(A_i, A_j) = \frac{(A_i *A_j)}{GCD(A_i,A_J)}

From (1), \frac{(A_i *A_j)}{GCD(A_i,A_J)} = 2*GCD(A_i, A_j)

=> A_i * A_j = 2*GCD(A_i, A_j) *GCD(A_i, A_j)---(2)

As we all know that GCD(A_i, A_j) must divide both A_i and A_j perfectly i.e,

A_i = C_{i}*GCD(A_i,A_j)---(3)

A_j = C_{j}*GCD(A_i,A_j)---(4)

where C_{i}\geq1 and C_j\geq1 are integers constant for A_i and A_j.

Now, substitute the values of A_i and A_j in equation (2) then we get,

C_i * C_j = 2

As C_i and C_j cannot be fraction then either C_i =1 and C_j=2 or C_i =2 and C_j=1

If you put the values of C_i and C_j in equations (3) and (4), then you will get either

A_i = 2*A_j or A_j = 2*A_i.

### Time Complexity : O(n)

# SOLUTIONS LINKS:

## Author's Solution

```
for _ in range(int(input())):
n = int(input())
A = [int(x) for x in input().split()]
d = {}
cnt = 0
for i in A:
if i in d:
d[i]+=1
else:
d[i] = 1
for i in d:
if i*2 in d:
cnt += d[i]*d[i*2]
print(cnt)
```

## Tester's Solution

```
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
ll T;
cin>>T;
while(T--) {
ll n, cnt=0;
cin>>n;
ll A[n];
for(ll i=0; i<n; i++) cin>>A[i];
unordered_map<int, int> freq;
for(ll i=0; i<n; i++){
freq[A[i]]++;
}
for( auto x : freq){
ll y = x.first;
if(freq.find(2*y)!=freq.end())
cnt+= freq[y]*freq[2*y];
}
cout<<cnt<<endl;
}
return 0;
}
```

If you have better approach, please do not hesitate to share with us. All the suggestions are welcome.