 # CHEFNUM1 - Editorial

Author: Anjani Kumar

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

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;
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;
}