Coprime to N in a Range — Solution & Editorial

Back to the Problem

Factor N to its distinct primes, then inclusion–exclusion: count multiples of each squarefree product of primes, alternating signs. Use prefix difference over the range.

Complexity: O(2^ω(N))