Anyone please explain the maths behind the bonus task of this problem…

bonus task is “to count total number of valid pairs” of equation LCM(a,b) + GCD(a,b) = x;

problem link :- https://codeforces.com/contest/1325/problem/A

1 Like

can you help me to find any valid pair (a, b) such that

LCM(a, b) + gcd(a, b) = x

and

GCD(a, b) != min(a, b)

I think GCD(a,b) == min(a,b) (must condition not very sure)

for it you can iterate over all the factors of X with sqrt(x) complexity

1 Like