poj 1286 Necklace of Beads【polya定理+burnside引理】

和poj 2409差不多，就是k变成3了，详见

还有不一样的地方是记得特判n==0的情况不然会RE

#include<iostream>

#include<cstdio>

using namespace std;

long long n,ans;

long long ksm(long long a,long long b)

{

	long long r=1;

	while(b)

	{

		if(b&1)

			r=r*a;

		a=a*a;

		b>>=1;

	}

	return r;

}

long long gcd(long long a,long long b)

{

	return !b?a:gcd(b,a%b);

}

int main()

{

	while(scanf("%lld",&n)&&n!=-1)

	{

		if(!n)

		{

			puts("0");

			continue;

		}

		ans=(n&1)?ksm(3,n/2+1)*n:ksm(3,n/2+1)*n/2+ksm(3,n/2)*n/2;

		for(int i=1;i<=n;i++)

			ans+=ksm(3,gcd(i,n));

		printf("%lld\n",ans/2/n);

	}

	return 0;

}

巴特西

poj 1286 Necklace of Beads【polya定理+burnside引理】

最新文章

热门文章