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: $$ \frac{x}{y} $$ where $1 \leq x \leq n$, $1 \leq y \leq m$, and $x$, $y$ are integers. A real number is an infinitely repeating pure decimal if it can be written in the form $a.\overline{c_1c_2c_3\ldots c_{p-1}c_p}$ where $a$ is an integer, and $c_i$ are the digits in base $k$. For example, in the decimal system, $0.45454545\ldots = 0.\overline{45}$ is an infinitely repeating pure decimal because it can be represented by fractions such as $\frac{5}{11}$, $\frac{10}{22},\ldots$ However, in the decimal system, $0.1666\ldots=0.1\overline{6}$ is not an infinitely repeating pure decimal as it cannot be represented by the fraction $\frac{1}{6}$. ### Input - One line containing three positive integers $n$, $m$, $k$. ### Output - Output a single integer, the answer. ### Example Input: ``` 2 6 10 ``` Output: ``` 4 ``` Explanation: - There are $4$ numbers: + $\frac{1}{1}=1.\overline{0}$ + $\frac{1}{3}=0.\overline{3}$ + $\frac{2}{1}=2.\overline{0}$ + $\frac{2}{3}=0.\overline{6}$ Input 2: ``` 23333 666666 310 ``` Output 2: ``` 5089564081 ``` ### Constraints In each test case: - $1 \le T \le 10, 1 \le n \le 30000$.
Test $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 \times 10^5$ $\le 1000$
15 $\le \times 10^5$
16 $\le 10^6$ $\le 10^8$ $\le 100$
17 $\le \times 10^6$ $\le 1000$
18 $\le \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