http://poj.org/problem?id=1286
题意：求用3种颜色给n个珠子涂色的方案数。polya定理模板题。
#include <stdio.h>
#include <math.h> long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
int main()
{
long long n;
while(~scanf("%lld",&n))
{
if (n==-)
break;
if (n <= )
{
printf("0\n");
continue;
}
long long ans = ;
for (int i = ; i < n; i++)
{
ans+=pow(,gcd(i,n));
}
if (n&)
ans+=n*pow(,n/+);
else
{
ans+=n/*pow(,n/)+n/*pow(,n/+);
}
printf("%lld\n",ans/n/);
}
return ;
}
同类型的题：
Let it Bead
http://poj.org/problem?id=2409
#include <stdio.h>
#include <math.h>
long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
/*long long pow(long long a,long long b)
{
long long res = 1;
while(b)
{
if (b&1)
res*=a;
a*=a;
b>>=1;
}
return res;
}*/
int main()
{
int n,k;
while(~scanf("%d%d",&k,&n))
{
if (k==&&n==)
break;
long long ans = ;
for (int i = ; i < n; i++)
{
ans+=pow(k,gcd(i,n));
}
if (n&)
ans+=n*pow(k,n/+);
else
{
ans+=n/*pow(k,n/)+n/*pow(k,n/+);
}
printf("%lld\n",ans/n/);
}
return ;
}