Strange Triples

题意翻译

- 称一个三元组 $(a,b,n)$ 是好的当且仅当 $\dfrac{\operatorname{concat}(a,n)}{\operatorname{concat}(n,b)}=\dfrac ab$，其中 $\operatorname{concat}(x,y)$ 表示拼接 $x,y$，如 $\operatorname{concat}(11,4)=114$。 - 给定 $A,B,N$，求满足 $a\in[1,A),b\in[1,B),n\in[1,N)$ 的好的三元组数量。 - $1\le A,B\le10^5$，$1\le N\le10^9$。

题目描述

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

输入输出样例

输入样例 #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

说明

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

**题目大意：**

三元组 $(a,b,n)$ 被称为奇怪的当且仅当 $\frac{\operatorname{concat}(a,n)}{\operatorname{concat}(n,b)}=\frac{a}{b}$ 成立，其中 $\operatorname{concat}(x,y)$ 表示将 $x,y$ 拼接起来，例如 $\operatorname{concat}(11,4)=114$。给定 $A,B,N$，求满足 $a\in[1,A),b\in[1,B),n\in[1,N)$ 的奇怪三元组的数量。其中 $1\le A,B\le10^5$，$1\le N\le10^9$。

**输入输出数据格式：**

- **输入格式：** 一行包含三个整数 $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$。**题目大意：** 三元组 $(a,b,n)$ 被称为奇怪的当且仅当 $\frac{\operatorname{concat}(a,n)}{\operatorname{concat}(n,b)}=\frac{a}{b}$ 成立，其中 $\operatorname{concat}(x,y)$ 表示将 $x,y$ 拼接起来，例如 $\operatorname{concat}(11,4)=114$。给定 $A,B,N$，求满足 $a\in[1,A),b\in[1,B),n\in[1,N)$ 的奇怪三元组的数量。其中 $1\le A,B\le10^5$，$1\le N\le10^9$。 **输入输出数据格式：** - **输入格式：** 一行包含三个整数 $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$。