暴力版
#include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef long long LL; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } LL polya(int m,int n) //m color ,n number { LL tot=0; //方案数 for(int i=1;i<=n;i++) tot+=pow(m,gcd(n,i)); tot/=n; if(n%2!=0) tot+=pow(m,(n+1)/2); //odd else tot+=(pow(m,n/2)+pow(m,n/2+1))/2; return tot/2; }欧拉函数优化版:
可以从gcd优化
d=gcd(n,i) 都是n约数
且对于d来说，设有x个d
那么可以枚举n的约数，于是tot+=x*gcd(m,d) 就行了
在O(sqrt(n)) 的复杂度就好了
而x的值就是欧拉函数φ(n/d)
#include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef long long LL; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int euler_phi(int n) { int res=1; for(int i=2;i*i<=n;i++) if(n%i==0) { //说明i|n n/=i,res*=i-1; while(n%i==0) n/=i,res*=i; //说明i^2|n } if(n>1) res*=n-1; return res; } LL polya(int m,int n) //m color ,n number { LL tot=0; //方案数 for(int i=1;i*i<=n;i++) //1~sqrt(n) { if(n%i) continue; //当i不是n的约数时就进入下一次循环 tot+=euler_phi(i)*pow(m,n/i); //d=gcd(n,i) d为n的因数，且有euler_phi(n/i)个 if(i*i!=n) tot+=euler_phi(n/i)*pow(m,i); //当i*i==n时，不必算两次 } tot/=n; if(n%2!=0) tot+=pow(m,(n+1)/2); //odd else tot+=(pow(m,n/2)+pow(m,n/2+1))/2; return tot/2; }