【POJ2409】Let it Bead
题意：用$m$种颜色去染$n$个点的环，如果两个环在旋转或翻转后是相同的，则称这两个环是同构的。求不同构的环的个数。
$n,m$很小就是了。
题解：在旋转$i$次后，循环节的个数显然是$gcd(i,n)$。
如果考虑翻转，我们将点从$0$到$n-1$标号，令其先以0到圆心的连线为对称轴翻转，再旋转i次，则原来编号为x的会变成$n-x+i?\mathrm{mod}?n$，令$n-x+i=x?\mathrm{mod}?n$，则$2x=i$或$2x=n+i$。
分奇偶性讨论一下循环节的个数即可。
最后套用Pólya定理。
其实n=2的情况是算重了的，不过你会发现每种情况都恰好被算了两次，所以就不用管了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
int n,m;
ll ans;
ll pw[35];
int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}
int main()
{
while(1)
{
scanf("%d%d",&m,&n);
if(!n&&!m) return 0;
int i;
for(pw[0]=i=1;i<=n;i++) pw[i]=pw[i-1]*m;
for(ans=i=0;i<n;i++)
{
ans+=pw[gcd(n,i)];
if(n&1) ans+=pw[(n+1)>>1];
else ans+=pw[(n>>1)+!(i&1)];
}
printf("%lld\n",ans/2/n);
}
}