Polya定理

02.09 考试第一题是 Polya定理，洛谷上的模板 (P4980 【模板】Polya) 定理是求 n 点环染 n 种颜色的本质不同的方案数，而考试考的是 给定 n , m , 在 size 为 n 的环上染 m 种颜色的方案数

首先呢，这是到群论的题，直接上 Polya 定理的公式

\(\frac{1}{n} \sum_{i=1}^{n} { m^{xi} }\)
其中 n 为置换数， m 为染色的种类数， xi 为每个置换的循环数
这是公式

关于这道题， 根据找规律每个置换的循环数是 __gcd(i , n) , 所以暴力是 O(n t) 的 （t 为多组数据）
所以我们要优化，改为枚举 Gcd
所以公式改为
\(\frac{1}{n} \sum_{d|n} \phi(n/d) m^d\)
看起来就是狄利克雷卷积，其实暴力就可以过了

再就是根号n的求 phi 函数
公式为
\(\phi(n) = n \prod_{i = 1}^{k}(1-\frac{pi-1}{pi})\)
我们根号n 的枚举 i , 每次都先得到的就是质因子 ， 再把 n 的质因子从n中消去，剩下的就是更大的质因子了,类似于筛质数的操作

代码：

#include <bits/stdc++.h>
#define ll long long 
#define int ll 
#define E 100007
#define M 1000000007
using namespace std ;
ll read() {
    ll s = 0 , f = 1 ; char ch ; 
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -1) ; 
    for(s = ch - '0' ; isdigit(ch = getchar()) ; s = s * 10 + ch - '0') ; 
    return s * f ; 
}
void putit(ll x) {
    if(x < 0) putchar('-') , x = -x ; 
    if(x > 9) putit(x / 10) ; 
    putchar(x % 10 + '0') ; 
}
ll ksm(ll d , ll z) {
    ll res = 1 ;
    while(z) { 
        if(z & 1) res = res * d % M ; 
        d = d * d % M ; 
        z >>= 1 ; 
    }
    return res ; 
}   
ll n , m ; 
ll P(ll xx) { return ksm(m , xx) ; }
ll phi(ll x) {
    ll sqr = sqrt(x) , rt = x ; 
    for(int i = 2 ; i <= sqr ; i ++) {
        if(x % i == 0) {
            rt = rt / i * (i-1) ; 
            while(x % i == 0) x /= i ; 
        }
    }
    if(x != 1) rt = rt / x * (x-1) ; 
    return rt ; 
}
signed main() {
    freopen("ak.in" , "r" , stdin) ; 
    freopen("ak.out", "w" ,stdout) ; 
    ll T = read() ; 
    while(T --) {
        n = read() , m = read() ; 
        ll rt = 0 , sqr = sqrt(n) ; 
        for(int i = 1 ; i <= sqr ; i ++) {
            if(n % i != 0) continue ; 
            ll d = i ; 
            (rt += phi(n/d) * P(d) % M) %= M ; 
            if(d * d == n) continue ; 
            d = n / i ; 
            (rt += phi(n/d) * P(d) % M) %= M ;          
        }
        (rt *= ksm(n , M-2)) %= M ; 
        putit(rt) , puts("") ; 
    }
    fclose(stdin) , fclose(stdout) ; 
    return 0 ; 
}
/*
5
5 3
6 2
8 4
20 9
30 11
*/
/*
51
14
8230
872010021
822671761
*/

Polya定理

原文：https://www.cnblogs.com/trouble-faker/p/10359340.html