Problem link: 1796F - Странные тройки
Let $$$p =$$$ number of digits of $$$n$$$, $$$q =$$$ number of digits of $$$b$$$, we have $$$n=\frac{a \cdot b \cdot (10^{p}-1)}{a \cdot 10^{q}-b}$$$, by checking every pair of possible $$$(a, b, p)$$$ we have a $$$O(A \cdot B \cdot log(N))$$$ solution, but it will get TLE.
We can modify this solution slightly: let $$$c=gcd(a, b)$$$, $$$k=\frac{a}{c}$$$, we have $$$n=\frac{k \cdot b \cdot (10^{p}-1)}{k \cdot 10^{q}-(b/c)}$$$, because $$$gcd(k, k \cdot 10^{q}-(b/c))=gcd(k, b/c)=gcd(a/c, b/c)=gcd(a, b)/c=1$$$, we have $$$k \cdot 10^{q}-(b/c)$$$ is divisor of $$$b \cdot (10^{p}-1)$$$, therefore, by pre-calculate factors for numbers in range $$$[1, 100000]$$$ and in $$${999999, 9999999, 99999999, 999999999}$$$, we can check answer for $$$b$$$ in $$$O(\sigma(b) \cdot 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 \cdot log(B) \cdot 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 $$$34KB$$$), and for $$$b$$$ which is not hardcoded, we can only check for $$$a=10^{t} \cdot 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: 195426974
