A2059. 循环之美
编程题
NOI/NOI+/CTSC
知识点
题目描述
牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 $k$ 进制下，一个数的小数部分是纯循环的，那么它就是美的。现在，牛牛想知道：对于已知的十进制数 $n$ 和 $m$，在 $k$ 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac xy$ 表示,其中 $1≤x≤n,1≤y≤m$，且 $x,y$ 是整数。一个数是纯循环的，当且仅当其可以写成以下形式：
$$a.\dot{c_1} c_2 c_3 \dots c_{p - 1} \dot{c_p}$$
其中，$a$ 是一个整数，$p≥1$；对于 $1≤i≤p$，$c_i$ 是 $k$ 进制下的一位数字。
例如，在十进制下，$0.45454545……=0.\dot {4} \dot {5}$ 是纯循环的，它可以用 $\frac {5}{11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666……=0.1\dot6$ 则不是纯循环的，它可以用 $\frac 16$ 等分数表示。需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环；而一个小数部分非 $0$ 的有限小数不是纯循环的。
$$a.\dot{c_1} c_2 c_3 \dots c_{p - 1} \dot{c_p}$$
其中，$a$ 是一个整数，$p≥1$；对于 $1≤i≤p$，$c_i$ 是 $k$ 进制下的一位数字。
例如，在十进制下，$0.45454545……=0.\dot {4} \dot {5}$ 是纯循环的，它可以用 $\frac {5}{11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666……=0.1\dot6$ 则不是纯循环的，它可以用 $\frac 16$ 等分数表示。需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环；而一个小数部分非 $0$ 的有限小数不是纯循环的。
输入格式
只有一行，包含三个十进制数 $N,M,K$ 意义如题所述。
输出格式
一行一个整数，表示满足条件的美的数的个数。
输入输出样例
输入 #1
2 6 10
输出 #1
4
说明/提示
### 样例解释
满足条件的数分别是：
$\frac 11=1.0000\ldots$
$\frac 13=0.3333\ldots$
$\frac 21=2.0000\ldots$
$\frac 23=0.6666\ldots$
$\frac 11$ 和 $\frac 22$ 虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，$\frac 13$ 和 $\frac 26$ 也只计数一次。
### 数据范围
对于所有的测试点，保证 $1\leq n\leq 10^9$，$1\leq m \leq 10^9$，$2\leq k \leq 2\times 10^3$。
对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：
| 测试点编号 | $n$ | $m$ | $k$ |
| :--------: | :-----------------: | :---------: | :---------: |
| $1$ | $\leq 10$ | $\leq 20$ | $=2$ |
| $2$ | $\leq 100$ | $\leq 10^4$ | $=2$ |
| $3$ | $\leq 10^3$ | | $=2$ |
| $4$ | $\leq 10^4$ | | $=2$ |
| $5$ | $\leq 10$ | $\leq 20$ | $=3$ |
| $6$ | $\leq 100$ | $\leq 10^4$ | $=3$ |
| $7$ | $\leq 10^3$ | | $=3$ |
| $8$ | $\leq 10^4$ | | $=3$ |
| $9$ | $\leq 10$ | $\leq 20$ | $\leq 100$ |
| $10$ | $\leq 100$ | $\leq 10^4$ | $\leq 100$ |
| $11$ | $\leq 10^3$ | | $\leq 10^3$ |
| $12$ | $\leq 10^4$ | | |
| $13$ | $\leq 10^5$ | $\leq 10^8$ | $\leq 100$ |
| $14$ | $\leq 2\times 10^5$ | | $\leq 10^3$ |
| $15$ | $\leq 5\times10^5$ | | |
| $16$ | $\leq 10^6$ | $\leq 10^8$ | $\leq 100$ |
| $17$ | $\leq 2\times 10^6$ | | $\leq 10^3$ |
| $18$ | $\leq 5\times 10^6$ | | |
| $19$ | $\leq 10^7$ | $\leq 10^8$ | $100$ |
| $20$ | $\leq 2\times10^7$ | | $\leq 10^3$ |
| $21$ | $\leq 2\times10^7$ | | |
| $22$ | $\leq 10^8$ | $\leq 10^8$ | |
| $23$ | $\leq 10^8$ | $\leq 10^8$ | |
| $24,25$ | | | |
### 提示
这部分将提供一个将分数化为对应的小数的方法，如果你已经熟悉这个方法，你不必阅读本提示。
分数可以通过除法，用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起，设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第 $a$ 位和小数点后第 $b$ 位（特殊地：如果其中一个对应的商数位是个位，则认为 $a=0$；不妨设 $a<b$），则其循环部分可以用小数点后第 $a+1$ 位到小数点后第 $b$ 位的循环来表示。
例如：在十进制下，将 $\frac 5{11}$ 转化为小数时，个位开始的商数依次为 $4,5,4,\ldots$，对应的余数分别为 $6,5,6,\ldots$。余数第一次重复出现的位置是个位和小数点后第 $2$ 位,那么 $a=0,b=2$。
$a=0,b=2$ 即其循环部分可以用小数点第 $1$ 位到第 $3$ 位来表示。表示为：$\frac 5{11}=0.45454545\ldots=0.\dot4\dot5$。
在十进制下，将 $\frac 16$ 转化为小数时,个位开始的商数依次为 $1,6,6,\ldots$，对应的余数分别为 $4,4,4,\ldots$。余数第一次重复出现的位置是小数点后第 $1$ 位和小数点后第 $2$ 位,即其循环部分可以用小数点后第 $2$ 位来表示。表示为：$\frac 16=0.1666……=0.1\dot6$。
需要注意的是：商数重复出现并不代表进入了循环节。
满足条件的数分别是：
$\frac 11=1.0000\ldots$
$\frac 13=0.3333\ldots$
$\frac 21=2.0000\ldots$
$\frac 23=0.6666\ldots$
$\frac 11$ 和 $\frac 22$ 虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，$\frac 13$ 和 $\frac 26$ 也只计数一次。
### 数据范围
对于所有的测试点，保证 $1\leq n\leq 10^9$，$1\leq m \leq 10^9$，$2\leq k \leq 2\times 10^3$。
对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：
| 测试点编号 | $n$ | $m$ | $k$ |
| :--------: | :-----------------: | :---------: | :---------: |
| $1$ | $\leq 10$ | $\leq 20$ | $=2$ |
| $2$ | $\leq 100$ | $\leq 10^4$ | $=2$ |
| $3$ | $\leq 10^3$ | | $=2$ |
| $4$ | $\leq 10^4$ | | $=2$ |
| $5$ | $\leq 10$ | $\leq 20$ | $=3$ |
| $6$ | $\leq 100$ | $\leq 10^4$ | $=3$ |
| $7$ | $\leq 10^3$ | | $=3$ |
| $8$ | $\leq 10^4$ | | $=3$ |
| $9$ | $\leq 10$ | $\leq 20$ | $\leq 100$ |
| $10$ | $\leq 100$ | $\leq 10^4$ | $\leq 100$ |
| $11$ | $\leq 10^3$ | | $\leq 10^3$ |
| $12$ | $\leq 10^4$ | | |
| $13$ | $\leq 10^5$ | $\leq 10^8$ | $\leq 100$ |
| $14$ | $\leq 2\times 10^5$ | | $\leq 10^3$ |
| $15$ | $\leq 5\times10^5$ | | |
| $16$ | $\leq 10^6$ | $\leq 10^8$ | $\leq 100$ |
| $17$ | $\leq 2\times 10^6$ | | $\leq 10^3$ |
| $18$ | $\leq 5\times 10^6$ | | |
| $19$ | $\leq 10^7$ | $\leq 10^8$ | $100$ |
| $20$ | $\leq 2\times10^7$ | | $\leq 10^3$ |
| $21$ | $\leq 2\times10^7$ | | |
| $22$ | $\leq 10^8$ | $\leq 10^8$ | |
| $23$ | $\leq 10^8$ | $\leq 10^8$ | |
| $24,25$ | | | |
### 提示
这部分将提供一个将分数化为对应的小数的方法，如果你已经熟悉这个方法，你不必阅读本提示。
分数可以通过除法，用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起，设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第 $a$ 位和小数点后第 $b$ 位（特殊地：如果其中一个对应的商数位是个位，则认为 $a=0$；不妨设 $a<b$），则其循环部分可以用小数点后第 $a+1$ 位到小数点后第 $b$ 位的循环来表示。
例如：在十进制下，将 $\frac 5{11}$ 转化为小数时，个位开始的商数依次为 $4,5,4,\ldots$，对应的余数分别为 $6,5,6,\ldots$。余数第一次重复出现的位置是个位和小数点后第 $2$ 位,那么 $a=0,b=2$。
$a=0,b=2$ 即其循环部分可以用小数点第 $1$ 位到第 $3$ 位来表示。表示为：$\frac 5{11}=0.45454545\ldots=0.\dot4\dot5$。
在十进制下，将 $\frac 16$ 转化为小数时,个位开始的商数依次为 $1,6,6,\ldots$，对应的余数分别为 $4,4,4,\ldots$。余数第一次重复出现的位置是小数点后第 $1$ 位和小数点后第 $2$ 位,即其循环部分可以用小数点后第 $2$ 位来表示。表示为：$\frac 16=0.1666……=0.1\dot6$。
需要注意的是：商数重复出现并不代表进入了循环节。