Coprime to N in a Range

Difficulty: 1900 4000 ms 128 MB

number-theory

Count the integers in [L, R] that are coprime with N.

Input: one line with three integers L, R, N.

Output: the count of coprime integers.

Constraints:

• 1 ≤ L ≤ R ≤ 10¹²
• 1 ≤ N ≤ 10⁹

Sample Tests

1 10 6

3

1 1 5

1

Read the Editorial