#2085. 「NOI2016」循环之美

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在 kkk 进制下,一个数的小数部分是纯循环的,那么它就是美的。

现在,牛牛想知道:对于已知的十进制数 nnnmmm,在 kkk 进制下,有多少个数值上互不相等的纯循环小数,可以用分数 xy\frac x yyx 表示,其中 1≤x≤n,1≤y≤m1\le x\le n,1\le y\le m1xn,1ym,且 x,yx,yx,y 是整数。

一个数是纯循环的,当且仅当其可以写成以下形式:

a.c1˙c2c3…cp−1cp˙a.\dot{c_1} c_2 c_3 \ldots c_{p - 1} \dot{c_p}a.c1˙c2c3cp1cp˙

其中,aaa 是一个整数,p≥1p\ge1p1;对于 1≤i≤p1\le i\le p1ipcic_icikkk 进制下的一位数字。

例如,在十进制下,0.45454545=0.˙4˙5 是纯循环的,它可以用 511\frac 5 {11}1151022\frac{10}{22}2210 等分数表示;在十进制下,0.1666666=0.1˙6 则不是纯循环的,它可以用 16\frac 1 661 等分数表示。

需要特别注意的是,我们认为一个整数是纯循环的,因为它的小数部分可以表示成 000 的循环或是 k−1k-1k1 的循环;而一个小数部分非 000 的有限小数不是纯循环的。

输入格式

输入文件只有一行,包含三个十进制数 n,m,kn,m,kn,m,k,意义如题所述。

输出格式

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

样例

样例输入 1

2 6 10

样例输出 1

4

样例解释 1

满足条件的数分别是:

1/1=1.0000……1/1 = 1.0000 \ldots \ldots1/1=1.00001/3=0.3333……1/3 = 0.3333 \ldots \ldots1/3=0.33332/1=2.0000……2/1 = 2.0000 \ldots \ldots2/1=2.00002/3=0.6666……2/3 = 0.6666 \ldots \ldots2/3=0.6666

1/11/11/12/22/22/2 虽然都是纯循环小数,但因为它们相等,因此只计数一次;同样,1/31/31/32/62/62/6 也只计数一次。

样例输入 2

23333 666666 310

样例输出 2

5089564081

数据范围与提示

对于所有的测试点,保证 1≤n≤1091\le n\le 10^91n1091≤m≤1091\le m\le 10^91m1092≤k≤20002\le k\le20002k2000