Count the integers k with 1 <= k <= n that are coprime to m, that is, gcd(k, m) = 1.
One line with n and m.
Print one integer: the number of integers from 1 to n that are coprime to m.
1 <= n <= 10^12 1 <= m <= 10^12 The answer is at most n, so it fits in a signed 64-bit integer.
1000 ms256 MB
30 30
8
The numbers 1, 7, 11, 13, 17, 19, 23, 29.
100 12
33
Of the numbers 1 to 100, those not divisible by 2 or 3: 100 - 50 - 33 + 16 = 33.
