necklace of beads(置换群，polya).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int gcd(int x,int y) 
{
	if(x > y) {
		std::swap(x,y);
	}
	while(x) {
		int t = x;
		x = y % x;
		y = t;
	}
	return y;
}

int main()
{
	__int64 n,i;
	__int64 f3[41], sum;
	f3[0] = 1;	f3[1] = 3;
	for(i=2;i<=40;i++) {
		f3[i] = 3*f3[i-1];
	}
	while(scanf("%I64d", &n), n!=-1) {
		if(n == 0) {
			puts("0");
			continue;
		}
		int g = n+n;
		sum = 0;
		if(n%2) {
			sum += n*f3[1 + n/2];
		}
		else {
			sum += 2*n*f3[n/2];
		}
		sum += f3[n];
		for(i=1;i<n;i++) {
			sum += f3[ gcd(i,n) ];
		}
		printf("%I64d\n", sum/g);
	}
}