Strange Triples

10000ms

262144K

Description:

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:

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

Output:

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$$$.

Sample Input:

5 6 10

Sample Output:

Sample Input:

10 10 100

Sample Output:

Sample Input:

1 10 25

Sample Output:

Sample Input:

4242 6969 133333337

Sample Output:

Sample Input:

94841 47471 581818184

Sample Output:

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$$$).

Informação

Provedor Codeforces

Código CF1796F