CHEFNUM1 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Anjani Kumar

DIFFICULTY:

HARD

PREREQUISITES:

Math, Number Theory

EXPLANATION:

The given contdition is LCM(a,b)+GCD(a,b) = x, x is a postive integer \geq 2. So, 1 \leq a, b \leq x-1.

Also, L.G = a.b

Let’s continue with the 1^{st} condition.

L+G=x
\frac{a.b}{G} + G = x
a.b+G^2=x.G

Now since G divides a and b. Let,
a=K_{1}G, b=K_{2}G

{K_{1}G.K_{2}G+G^2=x.G}
K_{1}.K_{2} = \frac{x}{G}-1

It is clear that K_{1}.K_{2} = \frac{L}{G}. So,
\frac{L}{G} = \frac{x}{G} - 1.

And, L = G.(\frac{x}{G}-1)

L=G.y , where y=\frac{x}{G}-1.

Now we know that for every valid pair (a,b), G must divide x also.
If we count valid (K_{1}, K_{2}) we will have valid count of (a,b)

We state that valid (K_{1}, K_{2}) are only when GCD(K_{1},K_{2}) = 1 (Can you see why?)

One naive approach would be to

  • iterate over factors of x(excluding x as its own factor because GCD won’t be equal to x),
  • Find \frac{L}{G} and find its factors.
  • Count pairs where GCD(K_{1},K_{2})=1.

But we can do better than this. Notice that if either of K_{1} or K_{2} is a prime factor of \frac{L}{G}, GCD(K_{1},K_{2}) will always be 1.

Let P be the number of distinct prime factors of \frac{L}{G}, then number of valid (K_{1}, K_{2}) pairs will be 2^P for each L and G calculated from L = G.(\frac{x}{G}-1).

The algorithm goes like this:-

  • iterate over factors of x(excluding x as its own factor because GCD won’t be equal to x)
  • Find the number of distict prime factors of \frac{L}{G}, P
  • Add 2^P to the answer.

Time complexity:- O(\sqrt{x}.\sqrt\frac{L}{G}.log(\frac{L}{G}))
Space complexity:- O(1)

SOLUTION:

setter's solution 
#include <bits/stdc++.h>
 
using namespace std; 
 
// counts P, number of distinct factors of an integer 
uint64_t prime_factors(uint64_t n){
    uint64_t cnt=0;
    // root n time
    for(uint64_t i=2;i*i<=n;i++){
        if(n%i == 0){
            cnt++;
            //  log(n) time
            while(n%i == 0){
                n/=i;
            }
        }
    }
    if(n>=2)cnt++;
    return cnt;
}
 
// returns 2^P 
uint64_t cntPairs(uint64_t L,uint64_t G){
    // prime_factors - L AND G
    if (L % G != 0) 
       return 0; 
    uint64_t div = L/G; 
    // answer is 2^totalPrimeFactors(L/G) 
    return (1 << prime_factors(div)); // Much faster than pow(2,prime_factors(div))
}
 
int main(){    
    int t;
    cin >> t;
    while(t--) {
        uint64_t x; // 64 bit unsigned integer
        cin >> x;
        uint64_t ans=0;
 
        for(uint64_t g=1;g*g<=x;g++){ //iterate over factors of x in root(x) time
            if(x%g == 0){
                uint64_t p=x/g-1;
                uint64_t G=g;
                uint64_t L=p*G;
                ans+=cntPairs(L,G);
                if(g != x/g && g!=1){// as gcd can't be equal to x
                    // This is because if g is a factor of x then x/g is also a factor of x.
                    p=g-1;
                    L=p*(x/g);
                    G=x/g;
                    ans+=cntPairs(L,G);        
                }
            }
        }
        cout<< ans << '\n'; 
    }
    return 0; 
}