 # LGCD - Editorial

Practice

Contest

Author: Md Shahid

Tester: Soham Chakrabarti

Editorialist: Md Shahid

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)

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.

2 Likes

Ok let’s extend this now @L_returns

ok let’s extend this
a∗b= X * (gcd(a,b))^ Y )
now it implies that
a = X * b^(Y-1) … right means in array if a is present then X * a^(Y-1) must be prsent to satisfies above condition
for ex:
X =3 Y =4
then a * b = 3 * GCD(a , b) ^ 4 , we want.
now if in array “2” is present then " 3 * (2 ^(4-1)) = 3*(2^(3)) = 3*8 = 24 " must present

Can u prove it mathematically… @nuttela
@anon55659401 @samarthtandon plz see this