Burnside引理与Polya定理

例题A题解

Polya模板。
Polya定理给出，如果设有限集 \(D\) 的置换群为 \(G\)，\(C\) 是由全体用 \(m\) 种颜色为 \(D\) 中颜色染色的方案构成的集合，每个置换 \(\sigma\) 的循环总数是 \(c(\sigma)\)，那么 \(G\) 诱导的 \(C\) 的等价类数量 \(N=\frac{1}{|G|}\sum_{\sigma\in G}m^{c(\sigma)}\)。
在这道题中：

\(D\) 就是珠子的位置 \(0,1,\dots,n-1\)（这里从 \(0\) 开始计数），颜色数量是 \(k=n\)。
每个置换 \(\sigma_i=(i,2i,\dots,0),(i+k,2i+k,\dots,k)\dots\)（表示整体向右移 \(i\) 位的这个循环），一共有 \(n\) 个置换。
且有 \(c(\sigma_i)=\gcd(n,i)\)（我们知道一个循环长度应该是 \(\frac{lcm(n,i)}{i}\)，在一个置换中，所有的 \(i\) 都应该出现，故总共置换数应该是 \(\frac{n}{(\frac{lcm(n,i)}{i})}=\gcd(n,i)\)）。
所以最终答案是 \(ans=\frac{1}{n}\sum_{i=1}^nk^{\gcd(n,i)}\)。

但是这道题的 \(n\) 高达 \(10^9\)，这不直接T飞了？
怎么办？
考虑优化这个式子：
我们发现，对于 \(\gcd(n,i)\) 相同的 \(i\)，贡献是一样的，那么能不能在这上面优化呢？
设 \(\gcd(n,i) = x\)，那么就有 \(\gcd(\frac{n}{x},\frac{i}{x})=1\)，也就是说，我们要统计的 \(\gcd(n,i) = x\) 的个数就是 \(\gcd(\frac{n}{x},\frac{i}{x})=1\) 的个数。
后者显然是欧拉函数，也就是说，公约数为 \(x\) 的 \(i\) 有 \(\varphi(\frac{n}{x})\) 个。
那么我们枚举约数，答案变成 \(\frac{1}{n}\sum_{p|n}\varphi(\frac{n}{p})\times p\)。
然后就没了。

例题A代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch  =getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
int mod, n;
int qpow(int x,int a){int res = 1;for(;a;a >>= 1,x = x * x % mod)if(a & 1)res = res * x % mod;return res;}
int phi(int n){
    int ans = n;
    for(int i = 2;i * i <= n;i++){
        if(n % i == 0){
            ans = ans / i * (i - 1);
            while(n % i == 0)n /= i;
        }
    }
    if(n > 1)ans = ans / n * (n - 1);
    return ans;
}
signed main(){
    for(int Test = read();Test;Test--){
        n = read();mod = read();
        int ans = 0;
        for(int i = 1;i * i <= n;i++){
            if(n % i != 0)continue;
            ans = (ans + phi(i) * qpow(n,n / i - 1) % mod) % mod;
            if(i * i != n)ans = (ans + phi(n / i) * qpow(n,i - 1) % mod) % mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}