POJ 2409 Let it Bead ——Burnside引理

【题目分析】

裸题直接做。

一个长度为n，颜色为m的环，本质不同的染色方案是多少。

数据范围比较小，直接做就好了。

【代码】

#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);

	}

}