polya计数法
简单模板
?
void solve(int n,int c)
{
int ans = 0;
for (int i = 1; i <= n; i++) if (n % i == 0)
{
ans += fun(c, i) * euler(n / i);
}
if (n & 1) ans += n * fun(c, n / 2 + 1);
else ans += n / 2 * (fun(c, n / 2) + fun(c, n / 2 + 1));
cout << ans / (2 * n) << endl;
}
fun（）函数是快速幂运算，enler是求欧拉数
?
?
#include#include using namespace std; int fun(int a,int x) { int ans=1; while(x) { if(x&1) ans=ans*a; a=a*a; x>>=1; } return ans; } int euler(int n){ int res=n,a=n; for(int i=2;i*i<=a;i++){ if(a%i==0){ res=res/i*(i-1); while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } void solve(int n,int c) { int ans = 0; for (int i = 1; i <= n; i++) if (n % i == 0) { ans += fun(c, i) * euler(n / i); } if (n & 1) ans += n * fun(c, n / 2 + 1); else ans += n / 2 * (fun(c, n / 2) + fun(c, n / 2 + 1)); cout << ans / (2 * n) << endl; } int main() { int n,c; while(~scanf("%d%d",&c,&n)&&n&&c) { solve(n,c); } return 0; }
?