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