Burnside's Lemma

1. Set sum = 0.
2. For every rotation r from 0 to n - 1:
   1. Set cycles = gcd(n, r).
   2. Add c^cycles to sum modulo MOD.
3. Multiply sum by n^(MOD - 2) modulo MOD.
4. Print the result.

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const long long mod = 1000000007;

long long binpow(long long a, long long e) {
    long long result = 1;
    while (e > 0) {
        if (e & 1) {
            result = result * a % mod;
        }
        a = a * a % mod;
        e >>= 1;
    }
    return result;
}

void solve() {
    int n;
    long long c;
    cin >> n >> c;

    long long sum = 0;
    for (int r = 0; r < n; r++) {
        int cycles = gcd(n, r);
        sum = (sum + binpow(c, cycles)) % mod;
    }

    long long answer = sum * binpow(n, mod - 2) % mod;
    cout << answer << '\n';
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

Introduction

Problem or motivation

Konig's Theorem

Core concept

Main algorithm

Mental model and detailed walkthrough

Implementation

Common mistakes

Complexity