25742번 - The Beauty of Cycles 다국어

We say a base-$k$ real number is beautiful if the decimal part of the real number is purely cyclic.

Now we want to know given base-10 numbers $n,m$, how many distinct (in value) purely cyclic real numbers there are that can be represented by $\frac{x}{y}$ where $1 \leq x \leq n, 1 \leq y \leq m$, and $x,y$ are integers.

A real number is said to be purely cyclic if and only if it can be written in the form of $$\displaystyle \displaystyle a.\dot{c_1} c_2 c_3 \ldots c_{p-1} \dot{c_p}$$ where $a$ is an (base-$k$) integer, $p \geq 1$, and for $1 \leq i \leq p$, $c_i$ is a digit in base $k$.

For example, under base 10, $$\displaystyle 0.45454545\cdots = 0.\dot{4}\dot{5}$$ is purely cyclic and can be represented by $\frac{5}{11}$ or $\frac{10}{22}$. Under base 10, $$\displaystyle 0.166666\cdots = 0.1\dot{6}$$ is not purely cyclic but can be represented by fractions like $\frac{1}{6}$.

Attention: an integer is purely cyclic since its decimal part can be written as repeating 0s or repeating $k-1$s. A terminating decimal whose decimal part is non-zero is not considered to be purely cyclic.

Notes: In China, the repeating part of a repeating decimal is marked by one or two dots. In some countries, the repeating part is marked by a line above the repeating part.

The input consists of one line with three base-10 integers $n,m,k$ whose meanings are described in the problem description.

Output a line with an integer denoting the beautiful numbers satisfying all the constraints.

For all test cases, $1 \leq n \leq 10^9, 1 \leq m \leq 10^9, 2 \leq k \leq 2000$.