GCDANDLCM Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

2157

PREREQUISITES:

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:

Setter’s Solution
Tester’s Solution

2 Likes
2

It was a good question

3

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

4

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

5

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 AA + 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;

    }
    }
}
6

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
7

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
8

Thanks for pointing it out. I will correct it.

9

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
10

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

1 Like
11

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

12

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
13

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() {
// your code goes here
ll t;
cin>>t;
while(t–)
{
ll n,count=0;
cin>>n;
for(ll a=1;(aa)<=n;a++)
{
for(ll lcm=a;(lcmlcm)<=n;lcm+=a)
{
ll lcm_sq=lcmlcm;
ll a_sq=aa;
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(bb != 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;

}

14

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

15

ooh btw thanks 4 the response…

16

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
17

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)