POJ 2409 Let it Bead ——Burnside引理

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define F(i,j,k) for (int i=j;i<=k;++i)
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);}
int n,c;
ll pow[50],ans;
int main()
{
	while (scanf("%d%d",&c,&n)&&c&&n)
	{
		ans=0;
		pow[0]=1;
		F(i,1,n) pow[i]=pow[i-1]*c;
		F(i,0,n-1) ans+=pow[gcd(i,n)];
		if (n&1) ans+=n*pow[n/2+1];
		else
		{
			ans+=n/2*pow[n/2];
			ans+=n/2*pow[n/2+1];
		}
		ans/=2*n;
		printf("%lld\n",ans);
	}
}