Pólya 定理题解（by DeepSeek）

问题重述

给定一个个点、条边的环，每个顶点可以染种颜色（颜色编号与顶点数相同）。问有多少种本质不同的染色方案，其中本质不同定义为：两种染色方案若可以通过旋转相互转换，则视为相同。答案对取模。

数据范围：，。

解题思路

这是一个典型的群论计数问题，可以用 Pólya 计数定理（又称伯恩赛德引理）解决。环的旋转群是循环群，共有个置换（旋转个单位）。对于每个旋转（），它会把环上的点分成若干个循环，每个循环内的点颜色必须相同，才能在旋转后保持不变。循环的个数恰好是（因为旋转步，步长为，在模意义下形成的轨道长度为，所以循环数为）。因此，对于旋转，保持不变的染色方案数为。

根据伯恩赛德引理，本质不同的染色方案数为：

直接枚举是不可行的，因为可达。我们转而枚举的取值，其中是的约数。对于固定的，满足的的个数等于（因为，其中且）。因此，公式可以改写为：

等价地，令，则：

其中遍历的正因子。

由于可能较大（），其因子个数最多约（实际很小），我们可以枚举所有因子，计算欧拉函数，并用快速幂计算，然后求和，最后乘以的逆元（模）。

算法步骤

对每个测试数据：
- 找出的所有正因子（遍历到）。
- 对于每个因子，同时也考虑（去重）。
- 对每个因子，计算，可以用试除法分解并利用公式。
- 计算，累加到答案中。
- 最后乘以的模逆元（注意可能等于？但，所以逆元存在）。
输出答案。

复杂度分析

对于每个，枚举因子，但最大，，单次最多约 3 万次，可以接受。
，最坏情况，可行。
快速幂。

代码实现（C++14）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;

ll mod_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll phi(ll x) {
    ll res = x;
    for (ll p = 2; p * p <= x; ++p) {
        if (x % p == 0) {
            res = res / p * (p - 1);
            while (x % p == 0) x /= p;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

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

    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;

        vector<ll> divisors;
        for (ll i = 1; i * i <= n; ++i) {
            if (n % i == 0) {
                divisors.push_back(i);
                if (i != n / i) divisors.push_back(n / i);
            }
        }

        ll ans = 0;
        for (ll g : divisors) {
            ll cnt = phi(g);                    // 满足 gcd(n,k)=n/g 的 k 的个数
            ll term = mod_pow(n, n / g);
            ans = (ans + cnt % MOD * term) % MOD;
        }
        ans = ans * mod_pow(n % MOD, MOD - 2) % MOD;   // 除以 n
        cout << ans << '\n';
    }
    return 0;
}

验证样例

以为例：

因子：，，贡献。
：，，贡献。
总和，除以得，符合输出。

注意事项

模数是质数，小于，故逆元可用费马小定理。
欧拉函数的计算中，可能为，此时，处理正确。
使用 long long 防止乘法溢出（模乘用 %MOD 即可，因为 MOD 约 1e9，乘积约 1e18 在 long long 范围内）。

扩展思考

本题是 Polya 定理的模板题，核心是掌握群作用、循环分解、以及利用欧拉函数加速求和。类似问题可用于项链、手镯等的计数。