Finally, for a probability demo, Farhan wants to count how many integers in a (potentially huge) range are coprime to a given N, without scanning the whole range one by one. Given N and a range [L,R], count how many integers in [L,R] are coprime to N. N can be large, and the range [L,R] can be huge (up to 10^18), so you must factorize N (up to sqrt(N)) and then use inclusion-exclusion over N's distinct prime factors (Möbius-style) rather than iterating the whole range.
Input
Three integers N L R.
Output
Count of integers in [L,R] coprime to N.
Constraints
1 ≤ N ≤ 10^12, 1 ≤ L ≤ R ≤ 10^18
Sample Input
6 1 20
Sample Output
7
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.