#1791. 「NOI2016」循环之美

「NOI2016」循环之美

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在 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
4

满足条件的数分别是:

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 也只计数一次。

23333 666666 310
5089564081

数据范围与提示

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

对于每个测试点,有以下约束(其中留空的表示没有特殊的约束):

测试点编号 nn mm kk
1 10\le 10 20\le 20 =2=2
2 100\le 100 104\le 10^4
3 1000\le 1000
4 10000\le 10000
5 10\le 10 20\le 20 =3=3
6 100\le 100 104\le 10^4
7 1000\le 1000
8 10000\le 10000
9 10\le 10 20\le 20 100\le 100
10 100\le 100 104\le 10^4
11 1000\le 1000 1000\le 1000
12 10000\le 10000
13 105\le 10^5 108\le 10^8 100\le 100
14 2×105\le 2\times 10^5 1000\le 1000
15 5×105\le 5\times 10^5
16 106\le 10^6 108\le 10^8 100\le 100
17 2×106\le 2\times 10^6 1000\le 1000
18 5×106\le 5\times 10^6
19 107\le 10^7 108\le 10^8 100\le 100
20 2×107\le 2\times 10^7 1000\le 1000
21
22 108\le 10^8
23
24
25