Contest Code: CZIL2021
Question Code: COZP31
Question link: Nastia and The Pairs (Error ! Time_Out) | CodeChef
Solution Logic:
A good fraction is always smaller than 1, therefore a/(a+1) x (b+1)/b < 1, after simplifying we get that a<b.
We are interested in pairs (a,b) such that there exists an integer c where a/(a+1) x (b+1)/b = c / (c+1). Let’s isolate the term c in function of a and b:
c = (ab + a) / (b-a)
Since a<b, we can write b=a+d, for some positive integer d. The expression for c now becomes:
c = (a . (a+d+1)) / d
Let’s simplify common factors between each member of the numerator with the denominator:
- We can simplify at most x=gcd(a,d) from the term a / d.
- We can simplify at most y=gcd(a+d+1,d) from the term (a+d+1) / d. By the euclidean algorithm we know that gcd(a,b)=gcd(b,a-b), therefore y=gcd(a+1,d)
That means that to make c an integer, we can set d=x′⋅y′, where x′ is any divisor of a, and y′ any divisor of a+1. Since a and a+1 are coprime, they don’t have common divisors, and we’ll always get different values for dd.
Let’s brute force all integers aa from 1 to n, iterate over each divisor’s x′ of a and count the valid values of y′. Note that b≤n, therefore a+ x′⋅y′ ≤n, that means we have to count only the y ′≤ (n−a)/x′. If we store the divisors of each integer in increasing order in a vector, we can count all such y′ with binary search, or two pointers.