Euler's Totient

Difficulty: 1600 3000 ms 128 MB

math number-theory

Print φ(N): how many integers in [1, N] are coprime with N.

Input: one integer N.

Output: φ(N).

Constraints:

• 1 ≤ N ≤ 10¹²

Sample Tests

9

6

1

1

Read the Editorial