POJ 1286:
//Polya定理 #include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<stack> #include<set> #include<bitset> using namespace std; long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } long long pow(long long a,long long n) { if (n==0) return 1; long long result=1; for (long long i=1;i<=n;i++) result*=a; return result; } int main() { cin.sync_with_stdio(false); long long n,Ans[30]={0}; for (long long i=1;i<24;i++) { n=i; for (long long j=1;j<=n;j++) Ans[n]+=pow(3,gcd(j,n)); if (n%2==0) Ans[n]+=pow(3,n/2+1)*n/2+pow(3,n/2)*n/2; else Ans[n]+=pow(3,n/2+1)*n; Ans[n]=Ans[n]/2/n; } while (cin>>n&&n!=-1) { cout<<Ans[n]<<endl; } return 0; }POJ 2409:
//Polya定理 //POJ 1286的升级版 加了颜色 也是直接带公式 #include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<stack> #include<set> #include<bitset> using namespace std; long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } long long pow(long long a,long long n) { if (n==0) return 1; long long result=1; for (long long i=1;i<=n;i++) result*=a; return result; } int main() { cin.sync_with_stdio(false); long long n,c,Ans; while (cin>>c>>n) { if (c==0&&n==0) break; Ans=0; for (long long j=1;j<=n;j++) Ans+=pow(c,gcd(j,n)); if (n%2==0) Ans+=pow(c,n/2+1)*n/2+pow(c,n/2)*n/2; else Ans+=pow(c,n/2+1)*n; Ans=Ans/2/n; cout<<Ans<<endl; } return 0; }