#2085. 「NOI2016」循环之美

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

题目描述

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

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

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

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

其中,aa 是一个整数,p1p\ge1;对于 1ip1\le i\le pcic_ikk 进制下的一位数字。

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

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

输入格式

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

输出格式

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

样例

样例输入 1

2 6 10

样例输出 1

4

样例解释 1

满足条件的数分别是:

1/1=1.00001/1 = 1.0000 \ldots \ldots

1/3=0.33331/3 = 0.3333 \ldots \ldots

2/1=2.00002/1 = 2.0000 \ldots \ldots

2/3=0.66662/3 = 0.6666 \ldots \ldots

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

样例输入 2

23333 666666 310

样例输出 2

5089564081

数据范围与提示

对于所有的测试点,保证 1n1091\le n\le 10^91m1091\le m\le 10^92k20002\le k\le2000