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$$$.
The only line contains three integers $$$A$$$, $$$B$$$ and $$$N$$$ ($$$1 \le A, B \le 10^5$$$; $$$1 \le N \le 10^9$$$).
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$$$.
5 6 10
7
10 10 100
29
1 10 25
0
4242 6969 133333337
19536
94841 47471 581818184
98715
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$$$).
Name |
---|