Counting Necklaces — Solution & Editorial

Back to the Problem

Burnside's lemma over the rotation group: the answer is (1/N) ∑_d|N φ(N/d) K^d. Enumerate divisors in O(√N), compute totients, and divide by N with a modular inverse.

Complexity: O(√N · (log + √))

Watch out: Dividing by N under the modulus needs an inverse (N is coprime to the prime modulus).