题目：http://poj.org/problem?id=1286
真·Polya定理模板题；
写完以后感觉理解更深刻了呢。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int n;
ll ans;
ll pw(ll a,int b)
{
ll ret=;
for(;b;b>>=,a*=a)
if(b&)ret*=a;
return ret;
}
int gcd(int a,int b){return (a%b==)?b:gcd(b,a%b);}
ll rot(int n)
{
ll ret=;
for(int i=;i<n;i++)
ret+=pw(,gcd(i,n));
return ret;
}
ll d(int n)
{
if(n%)return (ll)n*pw(,(n-)/+);
return (ll)n/*(pw(,n/)+(ll)pw(,(n-)/+));
}
int main()
{
while()
{
scanf("%d",&n);
if(!n)
{
printf("0\n"); continue;//!
}
if(n==-)return ;
ans=(rot(n)+d(n))/(*n);
printf("%lld\n",ans);
}
}