# GCDANDLCM Editorial

Setter: Satyam
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

2157

None

# PROBLEM:

You are given an integer N.

You are asked to find total number of integer pairs (A,B) such that

• 1 \leq A,B \leq N
• A^2+B^2+gcd^2(A,B)+lcm^2(A,B)=N. Note that gcd^2(A, B) and lcm^2(A, B) denote the square of gcd and the square of lcm of numbers A and B respectively.

# EXPLANATION:

GCD Property: For two numbers A and B, we have:

gcd(A,B) \times lcm(A,B) = A \times B

Here we can loop A from 1 to \lfloor \sqrt{N} \rfloor, and for each value of A we can loop the LCM from A to \lfloor \sqrt{N} \rfloor with increment of A, since LCM would always be a multiple of A. This would cover all the possible values of A and lcm(A,B) and from this we can calculate the value of B as follows:

A^2 + B^2 + gcd^2(A,B) + lcm^2(A,B) = N \\ B^2(1 + \frac{A^2}{lcm^2(A,B)}) = N - A^2 - lcm^2(A,B) \\ B^2 = lcm^2(A,B) \times \frac{(N - A^2 - lcm^2(A,B))}{lcm^2(A,B) + A^2}

Now that we got a value of B^2, we first check if its a positive perfect square or not. If not we move to next iteration otherwise we calculate the value of B and check for two conditions:

• lcm(A,B) = LCM
• A^2 + B^2 + gcd^2(A,B) + lcm^2(A,B) = N

If both of these conditions satisfy, this means we found a pair (A,B) that satisfies the above equation. Like this we keep going to calculate the count of all possible pairs that satisfies this equation.

# TIME COMPLEXITY:

O(\sqrt{N}log\sqrt{N}), for each test case.

# SOLUTION:

2 Likes

It was a good question

https://www.codechef.com/viewsolution/67727216

time limit of this code was 2 sec but and this python code takes 8 sec but does it give ACâ€¦

plzz tell me what is happening

Editorialâ€™s Solution Giving ans=1 when N=10^10, but answer is 3, (50000,50000) ,(70000,10000),(10000,70000)

Can SomeOne Try to improve time for my code for numbers >10^8.
Hereâ€™s the code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int GCD(ll int A,ll int B)
{
if(A%B==0) return B;
else return GCD(B,A%B);
};
int LCM(ll int A,ll int B)
{
return AB/GCD(A,B);
};
//Program For Finding Pairs (A,B) such that A
A + BB + aa + bb == N for a given N.
int main() /
Till N=[1,10^6] program runs very fast. Gives Output in milliseconds.
For N>10^6 program takes more time depending on increasing value of N.
For N>=10^9 program will take several minutes to answer.
So values of N which are multiples of 100 & N>10=5 we have reduced N to much extent
for fast calculation. For Example if N=10^9, it will be reduced to 10^5,
if N=10^10 it will be reduced to 10^6 and pairs will be calculated */

{
ll int T; //count of Possible cases
cin>>T;
while(Tâ€“){
//ll int k=0;
ll int N; cin>>N;
ll int A,B,count=0; //cin>>N;
ll int s=sqrt( (N-2) /2);
//ll int z=sqrt(N/4);
cout<<â€śs = â€ś<<s<<â€ť â€ś;
if(N==2ss+2) {
//cout<<N<<â€ť â€ś;
count += 2; //k++;
cout<<â€ť(â€ť<<s<<","<<1<<")"<<" , ("<<1<<","<<s<<")"<<" , â€ś;
//cout<<k<<â€ť ";
cout<<count<<endl;
continue;
}
else{
if(N>=100000 && N%100==0){ //Reducing N>=10^5 and multiples of 100 to shorter numbers
int DivideBy100=0;
do {
N = N/100;
DivideBy100++;
}
while(N>100000 && N%100==0);
ll int s1=sqrt( (N-2) /2);
cout<<"s1 = â€ś<<s1<<â€ť ";

for(ll int i=1;i<=s1;i++){
A=i;
//if(A>k+1) continue;
ll int z1=sqrt(N-2*i*i);
if(i<=z1) z1=i;
else z1=sqrt(N-2*i*i);
//cout<<z<<" ";
for(ll int j=1;j<=z1;j++){ //j>=l no need if i>=j present
//if(z<=j || z1<=j) break;
B=j;
ll int a=GCD(A,B),b=LCM(A,B);
//cout<<A<<" "<<B<<" ";
//if(b>s1) break;
if( A*A + B*B + a*a + b*b == N){
//k++;
if(A==B) {count++; cout<<"("<<A*pow(10,DivideBy100)<<","<<B*pow(10,DivideBy100)<<")"<<" , ";}
else{count +=2; cout<<"("<<A*pow(10,DivideBy100)<<","<<B*pow(10,DivideBy100)<<")";
cout<<" , ("<<B*pow(10,DivideBy100)<<","<<A*pow(10,DivideBy100)<<")"<<" , ";}
//cout<<" "<<k<<" " ;
}
}

}

}
else { //repeating the above same process(except do while loop) for all N except (N>=100000 && N%100==0)

//cout<<z<<" ";
for(ll int i=1;i<=s;i++){
A=i;
ll int z1=sqrt(N-2*i*i);
if(i<=z1) z1=i;
else z1=sqrt(N-2*i*i);
//if(A>k+1) continue;
for(int j=1;j<=z1;j++){ //j>=l no need if i>=j present

B=j;
ll int a=GCD(A,B),b=LCM(A,B);
//if(b>s) break;
//cout<<A<<" "<<B<<" ";
if( A*A + B*B + a*a + b*b == N){
//k++;
if(A==B) {count++; cout<<"("<<A<<","<<B<<")"<<" , ";}
else{count +=2; cout<<"("<<A<<","<<B<<")"<<" , ("<<B<<","<<A<<")"<<" , ";}
//cout<<" "<<k<<" " ;
}
}

}
}

cout<<count<<endl;

}
}
}

The given expression can be manipulated by writing a , b , lcm in terms of gcd:
Let A = a * c , B = b * c , gcd = c
so the given expression will reduce finally to :
(1 + a * a)(1 + b * b)(c * c) = N
And then considering the bounds of a,b,c ,we can easily solve it.
(You can see that a,b,c here are explicit of each other thatâ€™s why this reduced equation simplifies the problem a lot that we can take any value of a , b ,c as long as it satisfies our equation).
My submission for reference

6 Likes

An alternate way to simplify the above equation

Let
A = k1 * g
B = k2 * g
g = gcd(A, B)

Therefore the original equation :

A ^ 2 + B ^ 2 + gcd(A, B) ^ 2 + lcm(A, B) ^ 2 becomes

(k1 * g) ^ 2 + (k2 * g) ^ 2 + g ^ 2 + (k1 * k2 * g ) ^ 2

( Using the fact lcm(A, B) = (A * B) / gcd(A, B) )

= g ^ 2 * (1 + k1 ^ 2) * (1 + k2 ^ 2)

Now we just have to loop through factors of N to find no of valid tuples (g, k1, k2)

3 Likes

Thanks for pointing it out. I will correct it.

My approach was as follows.

First find the maximum M of all N. Then loop for all values L of LCM from 1 to sqrt(M). For each L find all its factors, in sqrt(L) time. From each set of F factors find all pairs which satisfy the requirements for any N <= M, in O(F^3) time. Create and maintain a set of all non-zero pairs (N, number of solutions) as we go. As there are usually only a few factors, rarely more than log(L), the time taken to check the factors is negligible overall compared to the time to find them, making the algorithm O(sqrt(M) * sqrt(sqrt(M)). Then loop through the test cases, printing the result from the set for each N.
You can see my solution at CodeChef: Practical coding for everyone which passed in 0.39 seconds.

2 Likes

Actually python3.6 is slow compared to c++ so a time multiplier of 5x is applied , for java 2x â€¦

1 Like

So I tried This approach
We can Write
A^2 + B^2 + gcd^2(A,B) + lcm^(A,B) = N as
(A + B)^2 + ( lcm(A,B) - gcd(A,B) )^2 = N or
(A - B)^2 + ( lcm(A,B) + gcd(A,B) )^2 = N Given A*B= lcm(A,B)*gcd(A,B)

So if we assume A>=B then We can conclude that lcm(A,B) = A and gcd(A,B)=B means A is Multiple of B and we can further conclude that A+B=lcm(A,B)+gcd(A,B) and A-B=lcm(A,B)-gcd(A,B)
I wrote N as sum of two squares i.e N= x^2+ y^2 assuming x>=y
then We can Simply write A+B =x and A-B =Y and so on .
This is even Faster O(sqrt(N)) per Test Case but i am getting WA . HELP
My Approach

Another approach for the given problem :

Given : A^2 + B^2 + GCD(A,B)^2 + LCM(A,B)^2 = N

Using the relation that **GCD(A,B) * LCM(A,B) = A * B**
We can rearrange the equation and write it in a factored form:

Let GCD(A,B) = G and LCM(A,B) = L for simplicity:

=> (A^2 + G^2)*(1 + B^2/G^2) = N
Now if we assume A^2 + G^2 to be a factor F then (1 + B^2/G^2) would have to be N/F

**A^2 + G^2 = F         ---- 1**
**1 + B^2/G^2 = N/F     ---- 2**

*Observation 1* : Factor F should be a sum of two perfect squares.
*Observation 2* : N/F - 1  should be a perfect square.

Note : We can always calculate factors of N in O(sqrt(N)) time.

1 Like

can someone point out whats wrong with my code? it fails only for the last test case.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll gcd(ll a,ll b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
int main() {
ll t;
cin>>t;
while(tâ€“)
{
ll n,count=0;
cin>>n;
for(ll a=1;(aa)<=n;a++)
{
for(ll lcm=a;(lcm
lcm)<=n;lcm+=a)
{
ll lcm_sq=lcmlcm;
ll a_sq=a
a;
ll num=(lcm_sq)(n- lcm_sq - a_sq);
if(num <= 0)
continue;
ll denom= lcm_sq + a_sq;
if(num%denom != 0)
continue;
ll b_sq=(num/denom);
ll b=(ll)(sqrt(b_sq));
if(b
b != b_sq)
continue;
if(((a*b)/gcd(a,b))!=lcm) continue;
ll gcd_sq = gcd(a,b) * gcd(a,b);

if(a_sq + b_sq + lcm_sq + gcd_sq == n)
count++;
}
}
cout<<count<<endl;
}
return 0;

}

You say that A is a multiple of B, but you can have A = 6, B = 4, G = 2, L = 12.

ooh btw thanks 4 the responseâ€¦

wow! nice approach
I actually simplified in terms of gcd and pre-calculated the divisors of all numbers till 1e5 and for each number from 1 to root(n) I assumed each of its divisors to be the gcd and checked the corresponding B value.
Let gcd(A,B) = G
B = G * root[ { N - (AA) - (GG) } / { (AA) + (GG) } ].
[CodeChef: Practical coding for everyone]

1 Like

You can precalculate divisors faster than O(n\sqrt n) by iterating over the multiples of each number. That way the time complexity will be
O(n) + O(\frac{n}{2}) + O(\frac{n}{3}) + \cdots O(\frac{n}{n}) = O(nlogn)