← 返回题目列表

Codeforces · 1796/F

F. 奇怪的三元组

中文机器翻译题面 查看原题

如果等式 $$$\frac{an}{nb} = \frac{a}{b}$$$ 成立,我们称正整数三元组 ($$$a, b, n$$$) 为奇怪,其中 $$$an$$$ 是 $$$a$$$ 和 $$$n$$$ 的串联,而 $$$nb$$$ 是 $$$n$$$ 和 $$$n$$$ 的串联$$$b$$$。为了连接的目的,整数被认为不带前导零。

例如,如果 $$$a = 1$$$、$$$b = 5$$$ 且 $$$n = 9$$$,则三元组很奇怪,因为 $$$\frac{19}{95} = \frac{1}{5}$$$。但 $$$a = 7$$$、$$$b = 3$$$ 和 $$$n = 11$$$ 并不奇怪,因为 $$$\frac{711}{113} \ne \frac{7}{3}$$$。

给你三个整数 $$$A$$$、$$$B$$$ 和 $$$N$$$。计算奇怪三元组 $$$(a, b, n$$$) 的数量,使得 $$$1 \le a < A$$$、$$$1 \le b < B$$$ 和 $$$1 \le n < N$$$。

输入

唯一的一行包含三个整数 $$$A$$$、$$$B$$$ 和 $$$N$$$ ($$$1 \le A, B \le 10^5$$$; $$$1 \le N \le 10^9$$$)。

输出

打印一个整数 - 奇怪的三元组 $$$(a, b, n$$$) 的数量,使得 $$$1 \le a < A$$$、$$$1 \le b < B$$$ 和 $$$1 \le n < N$$$。

示例

输入 #1

5 6 10

输出 #1

7

输入 #2

10 10 100

输出 #2

29

输入 #3

1 10 25

输出 #3

0

输入#4

4242 6969 133333337

输出#4

19536

输入 #5

94841 47471 581818184

输出 #5

98715

注意

在第一个示例中,有 $$$7$$$ 奇怪的三元组:$$$(1, 1, 1$$$), ($$$1, 4, 6$$$), ($$$1, 5, 9$$$), ($$$2, 2, 2$$$), ($$$2, 5, 6$$$), ($$$3, 3, 3$$$) 和 ($$$4, 4, 4$$$)。