Loading [MathJax]/jax/output/CommonHTML/jax.js
The beauty of circulation - MarisaOJ: Marisa Online Judge
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 |
Topic
Math
Rating
2700
Solution (0)
Solution