Solution of 1796F by hard-coding

Revision en4, by YocyCraft, 2023-03-01 11:51:48

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

Code for generating values of b

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English YocyCraft 2023-03-01 18:04:35 2
en7 English YocyCraft 2023-03-01 12:25:09 14
en6 English YocyCraft 2023-03-01 12:24:26 285
en5 English YocyCraft 2023-03-01 12:11:59 13
en4 English YocyCraft 2023-03-01 11:51:48 623
en3 English YocyCraft 2023-03-01 11:43:32 49
en2 English YocyCraft 2023-03-01 11:42:02 4896
en1 English YocyCraft 2023-03-01 11:36:58 1034 Initial revision (published)