P1587 [NOI2016] The Beauty of Cycles

Niuniu (Niúniú) is a high school student who loves algorithm design. In his algorithms, he often performs computations with numbers that have fractional parts. Niuniu considers a number beautiful if, in base $k$, its fractional part is purely repeating. Now, given decimal numbers $n$ and $m$, he wants to know: in base $k$, how many numerically distinct purely repeating fractions can be written as a fraction $\frac x y$, where $1 \leq x \leq n$, $1 \leq y \leq m$, and $x, y$ are integers. A number is purely repeating if and only if it can be written in the following form: $$a.\dot{c_1} c_2 c_3 \dots c_{p - 1} \dot{c_p}$$ Here, $a$ is an integer, $p \geq 1$; for $1 \leq i \leq p$, $c_i$ is a single digit in base $k$. For example, in base 10, $0.45454545... = 0.\dot {4} \dot {5}$ is purely repeating; it can be represented by fractions such as $\frac {5}{11}$ or $\frac{10}{22}$. In base 10, $0.1666666... = 0.1\dot6$ is not purely repeating; it can be represented by $\frac 1 6$. Note that we consider an integer to be purely repeating, because its fractional part can be represented as a repeating $0$ or a repeating $k - 1$; however, a finite fraction with a nonzero fractional part is not purely repeating.

One line containing three decimal integers $N, M, K$ as described.

Output a single integer on one line, the number of beautiful numbers that satisfy the conditions.

### Sample Explanation The numbers that satisfy the conditions are: $\frac 1 1 = 1.0000...$ $\frac 1 3 = 0.3333...$ $\frac 2 1 = 2.0000...$ $\frac 2 3 = 0.6666...$ Although $\frac 1 1$ and $\frac 2 2$ are both purely repeating decimals, they are equal, so they are counted only once; similarly, $\frac 1 3$ and $\frac 2 6$ are counted only once. ### Constraints For all test points, it is guaranteed that $1 \leq n \leq 10^9$, $1 \leq m \leq 10^9$, $2 \leq k \leq 2 \times 10^3$. For each test point, the following constraints hold (a blank entry means no special constraint): ::cute-table{tuack} | Test point ID | $n$ | $m$ | $k$ | | :-----------: | :-----------------: | :---------: | :---------: | | $1$ | $\leq 10$ | $\leq 20$ | $=2$ | | $2$ | $\leq 100$ | $\leq 10^4$ | ^ | | $3$ | $\leq 10^3$ | | ^ | | $4$ | $\leq 10^4$ | | ^ | | $5$ | $\leq 10$ | $\leq 20$ | $=3$ | | $6$ | $\leq 100$ | $\leq 10^4$ | ^ | | $7$ | $\leq 10^3$ | | ^ | | $8$ | $\leq 10^4$ | | ^ | | $9$ | $\leq 10$ | $\leq 20$ | $\leq 100$ | | $10$ | $\leq 100$ | $\leq 10^4$ | ^ | | $11$ | $\leq 10^3$ | | $\leq 10^3$ | | $12$ | $\leq 10^4$ | | | | $13$ | $\leq 10^5$ | $\leq 10^8$ | $\leq 100$ | | $14$ | $\leq 2\times 10^5$ | | $\leq 10^3$ | | $15$ | $\leq 5\times10^5$ | | | | $16$ | $\leq 10^6$ | $\leq 10^8$ | $\leq 100$ | | $17$ | $\leq 2\times 10^6$ | | $\leq 10^3$ | | $18$ | $\leq 5\times 10^6$ | | | | $19$ | $\leq 10^7$ | $\leq 10^8$ | $100$ | | $20$ | $\leq 2\times10^7$ | | $\leq 10^3$ | | $21$ | ^ | | | | $22$ | $\leq 10^8$ | $\leq 10^8$ | | | $23$ | ^ | ^ | | | $24,25$ | | | | ### Hint This section provides a method to convert a fraction into its corresponding decimal expansion. If you are already familiar with this method, you do not need to read this part. A fraction can be converted to its corresponding decimal by division, dividing the numerator by the denominator. For some fractions, the division does not terminate; in such cases, during the ongoing division the remainder must eventually repeat. Starting from the remainder corresponding to the ones place of the quotient, suppose that for the first remainder to repeat, the positions of its two occurrences correspond to the $a$-th and $b$-th digits after the decimal point in the quotient (special case: if one of them corresponds to the ones place, take $a = 0$; assume $a < b$). Then its repeating part can be represented by the cycle from the $(a + 1)$-th digit to the $b$-th digit after the decimal point. For example: in base 10, when converting $\frac 5 {11}$ to a decimal, the quotient digits starting from the ones place are $4, 5, 4, \ldots$, and the corresponding remainders are $6, 5, 6, \ldots$. The positions of the first repeated remainder are the ones place and the $2$-nd digit after the decimal point, so $a = 0, b = 2$. $a = 0, b = 2$ means its repeating part can be represented by the cycle from the $1$-st to the $3$-rd digits after the decimal point. Thus: $\frac 5 {11} = 0.45454545... = 0.\dot4\dot5$. In base 10, when converting $\frac 1 6$ to a decimal, the quotient digits starting from the ones place are $1, 6, 6, \ldots$, and the corresponding remainders are $4, 4, 4, \ldots$. The positions of the first repeated remainder are the $1$-st and $2$-nd digits after the decimal point, which means its repeating part can be represented by the $2$-nd digit after the decimal point. Thus: $\frac 1 6 = 0.1666... = 0.1\dot6$. Note: a repeated quotient digit does not necessarily indicate that the repeating cycle has begun. Translated by ChatGPT 5