[NOI2016]循环之美

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在 $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$则不是纯循环的,它可以用 $1/6$ 等分数表示。需要特别注意的是,我们认为一个整数是纯循环的,因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环;而一个小数部分非 $0$ 的有限小数不是纯循环的。

输入输出格式

输入格式


只有一行,包含三个十进制数N,M,K意义如题所述,保证 1≤n≤10^9,1≤m≤10^9,2≤k≤2000

输出格式


一行一个整数,表示满足条件的美的数的个数。

输入输出样例

输入样例 #1

2 6 10

输出样例 #1

4

说明

满足条件的数分别是: ```cpp 1/1=1.0000…… 1/3=0.3333…… 2/1=2.0000…… 2/3=0.6666…… ``` 1/1 和 2/2 虽然都是纯循环小数,但因为它们相等,因此只计数一次;同样,1/3 和 2/6 也只计数一次。 ![](https://cdn.luogu.com.cn/upload/pic/2389.png) 这部分将提供一个将分数化为对应的小数的方法,如果你已经熟悉这个方法,你不必阅读本提示。 分数可以通过除法,用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起,设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第 a位和小数点后第 b 位(特殊地:如果其中一个对应的商数位是个位,则认为 a=0;不妨设 a