Strange Triples
Contest: Educational Codeforces Round 144 (Rated for Div. 2)
Difficulty rating: 2900
Tags: brute force, math, number theory

Let's call a triple of positive integers ($$$a, b, n$$$) strange if the equality $$$\frac{an}{nb} = \frac{a}{b}$$$ holds, where $$$an$$$ is the concatenation of $$$a$$$ and $$$n$$$ and $$$nb$$$ is the concatenation of $$$n$$$ and $$$b$$$. For the purpose of concatenation, the integers are considered without leading zeroes.

For example, if $$$a = 1$$$, $$$b = 5$$$ and $$$n = 9$$$, then the triple is strange, because $$$\frac{19}{95} = \frac{1}{5}$$$. But $$$a = 7$$$, $$$b = 3$$$ and $$$n = 11$$$ is not strange, because $$$\frac{711}{113} \ne \frac{7}{3}$$$.

You are given three integers $$$A$$$, $$$B$$$ and $$$N$$$. Calculate the number of strange triples $$$(a, b, n$$$), such that $$$1 \le a < A$$$, $$$1 \le b < B$$$ and $$$1 \le n < N$$$.

Input format:
The only line contains three integers $$$A$$$, $$$B$$$ and $$$N$$$ ($$$1 \le A, B \le 10^5$$$; $$$1 \le N \le 10^9$$$).

Output format:
Print one integer — the number of strange triples $$$(a, b, n$$$) such that $$$1 \le a < A$$$, $$$1 \le b < B$$$ and $$$1 \le n < N$$$.

Constraints:
Time limit: 10.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are $$$7$$$ strange triples: $$$(1, 1, 1$$$), ($$$1, 4, 6$$$), ($$$1, 5, 9$$$), ($$$2, 2, 2$$$), ($$$2, 5, 6$$$), ($$$3, 3, 3$$$) and ($$$4, 4, 4$$$).

Example input:
5 6 10

Example output:
7

Example input:
10 10 100

Example output:
29

Editorial:
Let $$$|n|$$$ be the length of number $$$n$$$. Then $$$$$$ \frac{an}{nb} = \frac{a}{b} \Leftrightarrow (a \cdot 10^{|n|} + n) b = a (n \cdot 10^{|b|} + b)$$$$$$ Let $$$g = \gcd(a, b)$$$ then $$$a = a' g$$$ and $$$b = b' g$$$ and we get $$$$$$ (a \cdot 10^{|n|} + n) b = a (n \cdot 10^{|b|} + b) \Leftrightarrow g^2 a' b' \cdot 10^{|n|} + g n b' = g a' n \cdot 10^{|b|} + g^2 a' b' \Leftrightarrow $$$$$$ $$$$$$ \Leftrightarrow g a' b' \cdot 10^{|n|} + n b' = a' n \cdot 10^{|b|} + g a' b' $$$$$$
Note that the right part is divisible by $$$a'$$$, so the left part should as well. Then we can see that $$$n$$$ should be divisible by $$$a'$$$, since $$$\gcd(b', a') = 1$$$. Let's say $$$n = n' a'$$$ then divide both sides by $$$a'$$$. We get $$$$$$ g a' b' \cdot 10^{|n|} + n' a' b' = a' n' a' \cdot 10^{|b|} + g a' b' \Leftrightarrow g b' \cdot 10^{|n|} + n' b' = a' n' \cdot 10^{|b|} + g b' $$$$$$
Let's rearrange it and get the following: $$$$$$ n' b' = a' n' \cdot 10^{|b|} - b (10^{|n|} - 1) $$$$$$ $$$$$$ b' = a' \cdot 10^{|b|} - \frac{b (10^{|n|} - 1)}{n'} $$$$$$
Since $$$b'$$$ is integer, then $$$\frac{b (10^{|n|} - 1)}{n'}$$$ should be integer. In other words, we can define $$$n' = k_1 k_2$$$ such that $$$b$$$ is divisible by $$$k_1$$$ and $$$(10^{|n|} - 1)$$$ is divisible by $$$k_2$$$ and $$$k_1$$$ is minimum possible.
Since $$$(10^{|n|} - 1)$$$ has a very special structure, let's iterate over all lengths $$$|n|$$$ ($$$1 \le |n| \le 9$$$) and all divisors $$$k_2$$$ of $$$(10^{|n|} - 1)$$$ for a fixed $$$|n|$$$. Let's say $$$d = \frac{b}{k_1}$$$ and $$$r = \frac{(10^{|n|} - 1)}{k_2}$$$. Then $$$$$$ b' = a' \cdot 10^{|b|} - d \cdot r $$$$$$
For a fixed $$$|n|$$$ and $$$k_2$$$ we know $$$r$$$, but don't know $$$d$$$. So, let's just iterate over all possible $$$d$$$ ($$$1 \le d \le 10^5$$$) and let's also iterate over all $$$|b|$$$, since $$$|b|$$$ is small ($$$|d| \le |b| \le 5$$$, since $$$d$$$ is a divisor of $$$b$$$). Next step is following: let's look at previous equation, but modulo $$$10^{|b|}$$$: $$$$$$ b' \equiv - d \cdot r \pmod {10^{|b|}} $$$$$$
Since $$$b' \le b < 10^{|b|}$$$ then there is a unique solution to the previous module equation, or: $$$$$$ b' = 10^{|b|} - (d \cdot r) \bmod {10^{|b|}} $$$$$$
Now we know exact value $$$b'$$$ and $$$|b|$$$, so now the time to guess $$$g$$$ (let's recall that $$$b = b' g$$$). Since we fixed $$$|b|$$$, then $$$10^{|b| - 1} \le b' g < 10^{|b|}$$$, or $$$$$$ \left\lceil \frac{10^{|b| - 1}}{b'} \right\rceil \le g \le \left\lfloor \frac{10^{|b|} - 1}{b'} \right\rfloor$$$$$$ Let's name the left border as $$$lb$$$ and right border $$$rb$$$, so inequality earlier is $$$lb \le g \le rb$$$.
But we can make constrains even tighter: note that $$$b = b' g$$$, but lately, we said that $$$d = \frac{b}{k_1}$$$ or $$$b = d k_1$$$. So, $$$b' g = d k_1$$$, or $$$g$$$ should be divisible by $$$dd = \frac{d}{\gcd(d, b')}$$$.
In total, we can iterate $$$g$$$ in range $$$[\left\lceil \frac{lb}{dd} \right\rceil \cdot dd, \dots, \left\lfloor \frac{rb}{dd} \right\rfloor \cdot dd]$$$ with step $$$dd$$$, since we are interested only in $$$g$$$ divisible by $$$dd$$$.
Now we have enough variables to construct a triple: we know $$$b'$$$ and $$$g$$$, so $$$b = b' g$$$. If $$$b$$$ is already big ($$$b \ge B$$$), we can skip that candidate. Also, we can calculate $$$k_1 = \frac{b}{d}$$$ and check that pair $$$(k_1, k_2)$$$ is valid, i. e. $$$k_1$$$ is really minimum possible. We can understand it by checking that $$$\gcd(k_1, r) = 1$$$ (otherwise, we can reduce $$$k_1$$$ by $$$\gcd(k_1, r)$$$).
Value $$$a'$$$ can be calculated from one of the formulas above as $$$a' = \frac{d \cdot r + b'}{10^{|b|}}$$$. After that, we calculate $$$a = a' g$$$ and check that $$$a$$$ is not too big. Value $$$n$$$ can be calculated as $$$n = k_1 k_2 a' = \frac{b}{d} k_2 a'$$$.
At last, we should check that the given triple satisfy all remaining assumptions we made: $$$n$$$ is not too big, $$$\gcd(a', b')$$$ is really $$$1$$$ and length of calculated $$$n$$$ is exactly $$$|n|$$$ we fixed. If it's all fine, then we found a correct triple. It looks like, thanks to all previous checks, the triple we found is unique, but, just for safety, let's push them all in one set to get rid of copies.
Calculating complexity is not trivial, but let's note something: the total number of divisors $$$k_2$$$ of $$$10^{|n|} - 1$$$ for all $$$|n|$$$ is around $$$180$$$. For a fixed pair $$$(|n|, k_2)$$$, we iterate over all $$$d$$$ from $$$1$$$ to $$$B$$$ and for each $$$d$$$ we iterate $$$|b|$$$ from $$$|d|$$$ to $$$5$$$, but it's easy to prove that the total number of pairs $$$(d, |b|)$$$ is at most $$$1.3 \cdot B$$$. Now the last cycle: iteration of $$$g$$$ with step $$$dd$$$ where $$$dd = \frac{d}{\gcd(d, b')}$$$. If we assume that $$$\gcd(d, b')$$$ is quite small then $$$dd$$$ is proportional to $$$d$$$, and pairs $$$(d, g)$$$ are something like harmonic series with $$$O(B \log B)$$$ complexity. In total, the complexity is around $$$O(200 B \log{B})$$$.