Problem link: 1796F - Странные тройки
Let p = number of digits of n, q = number of digits of b, we have n=a*b*(10^p-1)/(a*10^q-b), by checking every pair of possible (a, b, p) we have a O(A*B*log(N)) solution, but it will get TLE.
We can modify this solution slightly: let c=gcd(a, b), k=a/c, we have n=k*b*(10^p-1)/(k*10^q-(b/c)), because gcd(k, k*10^q-(b/c))=gcd(k, b/c)=gcd(a/c, b/c)=gcd(a, b)/c=1, we have (k*10^q-(b/c)) is divisor of (b*(10^p-1)), therefore, by pre-calculate factors for numbers in range [1, 100000] and in {999'999, 9'999'999, 99'999'999, 999'999'999}, we can check answer for b in O(sigma(b)*185), where sigma(b) is the number of divisors of b, and 185=sum(p=1...9)(sigma(10^p-1)), and we can solve the problem in O(B*log(B)*185), but this solution still get TLE due to large constant factor of division and modular operations.
If we let A, B, N be their maximum value, we can see there are only 172104 possible valid tuples can be the answer, so we could solve the problem by hard-coding-- however, each pair of (a,b) will add about 10-20 bytes to the size of code, and we need 2-3MB to store all pairs, which exceed the limit of 64KB. By printing all valid tuples, we can see that for almost all pairs of (a,b), the value of a/b is some integer power of 10, and for other pairs, there are only 6143 different possible values of b. Therefore, we can hardcode these values (for 34 KB), and for b which is not hardcoded, we can only check for a=10^t*b (for every pair of (b, p) there are only 5 possible values of a), then we can solve the problem in 2000ms.
My submission: 195421691
