【poj 1286 Necklace of Beads】【具有對稱性的計數】【polya計數】【項鍊染色方案數】

【連結】

http://poj.org/problem?id=1286

【題意】

n個珠子串成一個圓，用三種顔色去塗色。問一共有多少種不同的塗色方法(翻轉，旋轉相同)

翻轉：如果n是奇數，則存在n中置換，每種置換包含n/2+1種循環(即輪換)。

            如果n是偶數，如果對稱軸過頂點，則存在n/2種置換，每種置換包含n/2種循環(即輪換)

 如果對稱軸不過頂點，則存在n/2種置換，每種置換包含n/2+1種循環(即輪換)

旋轉：n個點順時針或者逆時針旋轉i個位置的置換，輪換個數為gcd(n,i)

最後要:  ans/=(置換數)（|G|=n+n/2+n/2）

【代碼】

#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 6;
typedef long long ll;

ll gcd(ll a, ll b) {
	return b==0 ? a : gcd(b, a%b);
}

int main() {
	int n;
	while (~scanf("%d", &n), (n + 1)) {
		if (n == 0) {
			printf("0\n");
			continue;
		}
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += pow(1.0*3, 1.0*gcd(i, n));
		}
		if (n & 1)ans += n * pow(1.0*3,1.0*(n / 2 + 1));
		else ans += n / 2 * pow(3.0, 1.0*(n / 2 + 1)) + n / 2 * pow(3.0, n / 2);
		ans /= 2 * n;
		printf("%lld\n", ans);
	}
}