Codezilla Editorial: Error| Time Out

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.