#2085. 「NOI2016」循环之美

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

题目描述

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

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

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

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

其中, a 是一个整数, p\ge1 ;对于 1\le i\le p c_i k 进制下的一位数字。

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

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

输入格式

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

输出格式

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

样例

样例输入 1

2 6 10

样例输出 1

4

样例解释 1

满足条件的数分别是:

1/1 = 1.0000 \ldots \ldots

1/3 = 0.3333 \ldots \ldots

2/1 = 2.0000 \ldots \ldots

2/3 = 0.6666 \ldots \ldots

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

样例输入 2

23333 666666 310

样例输出 2

5089564081

数据范围与提示

对于所有的测试点,保证 1\le n\le 10^9 1\le m\le 10^9 2\le k\le2000

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

测试点编号 n m k
1 \le 10 \le 20 =2
2 \le 100 \le 10^4
3 \le 1000
4 \le 10000
5 \le 10 \le 20 =3
6 \le 100 \le 10^4
7 \le 1000
8 \le 10000
9 \le 10 \le 20 \le 100
10 \le 100 \le 10^4
11 \le 1000 \le 1000
12 \le 10000
13 \le 10^5 \le 10^8 \le 100
14 \le 2\times 10^5 \le 1000
15 \le 5\times 10^5
16 \le 10^6 \le 10^8 \le 100
17 \le 2\times 10^6 \le 1000
18 \le 5\times 10^6
19 \le 10^7 \le 10^8 \le 100
20 \le 2\times 10^7 \le 1000
21
22 \le 10^8
23
24
25