Loading [MathJax]/jax/output/CommonHTML/jax.js
The beauty of circulation - MarisaOJ: Marisa Online Judge

The beauty of circulation

Time limit: 2000 ms
Memory limit: 512 MB
Given three positive integers n, m, and k, count the number of infinitely repeating pure decimals that can be represented by the fraction: xy where 1≤x≤n, 1≤y≤m, and x, y are integers. A real number is an infinitely repeating pure decimal if it can be written in the form a.¯c1c2c3…cp−1cp where a is an integer, and ci are the digits in base k. For example, in the decimal system, 0.45454545…=0.¯45 is an infinitely repeating pure decimal because it can be represented by fractions such as 511, 1022,… However, in the decimal system, 0.1666…=0.1¯6 is not an infinitely repeating pure decimal as it cannot be represented by the fraction 16. ### Input - One line containing three positive integers n, m, k. ### Output - Output a single integer, the answer. ### Example Input: 2610 Output: 4 Explanation: - There are 4 numbers: + 11=1.¯0 + 13=0.¯3 + 21=2.¯0 + 23=0.¯6 Input 2: 23333666666310 Output 2: 5089564081 ### Constraints In each test case: - 1≤T≤10,1≤n≤30000.
Test n m k
1 ≤10 ≤20 =2
2 ≤100 ≤104
3 ≤1000
4 ≤10000
5 ≤10 ≤20 =3
6 ≤100 ≤104
7 ≤1000
8 ≤10000
9 ≤10 ≤20 ≤100
10 ≤100 ≤104
11 ≤1000 ≤1000
12 ≤10000
13 ≤105 ≤108 ≤100
14 ≤×105 ≤1000
15 ≤×105
16 ≤106 ≤108 ≤100
17 ≤×106 ≤1000
18 ≤×106
19 ≤107 ≤108 ≤100
20 ≤2×107 ≤1000
21
22 ≤108
23
24
25