## NOI '16 P3 - The Beauty of Cycles

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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

Now we want to know given base-10 numbers , how many distinct (in value) purely cyclic real numbers there are that can be represented by where , , and are integers.

A real number is said to be purely cyclic if and only if it can be written in the form of where is an (base-) integer, , and for , is a digit in base .

For example, under base 10, is purely cyclic and can be represented by or . Under base 10, is not purely cyclic but can be represented by fractions like .

Attention: an integer is purely cyclic since its decimal part can be written as repeating 0s or repeating 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.

#### Input Specification

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

#### Output Specification

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

#### Sample Input 1

2 6 10

#### Sample Output 1

4

#### Explanation of Sample 1

The beautiful numbers are , , , . Even though and are both purely cyclic, they are equal in value so they are only counted once. Similarly, and should also be counted once.

#### Sample Input 2

23333 666666 310

#### Sample Output 2

5089564081

#### Constraints

For all test cases, , , .

Items left blank means there are no special restrictions.

Test case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22,23
24,25