POJ 1286 Necklace of Beads Polya .

题目地址：http://poj.org/problem?id=1286

旋转+翻转，裸的算法

#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 n) { LL tot=0; //方案数 for(int i=1;i<=n;i++) tot+=pow(3,gcd(n,i)); tot/=n; if(n%2!=0) tot+=pow(3,(n+1)/2); //odd else tot+=(pow(3,n/2)+pow(3,n/2+1))/2; return tot/2; } int main() { int n; while(cin>>n&&n!=-1) if(n==0) cout<<0<<endl; else cout<<polya(n)<<endl; return 0; }