poj1286-polya计数、burnside定理

组合数学题目

就是一个手镯，用三种颜色图，可以旋转和翻转，求有多少方案。

建议先看看群、burnside定理，polya计数等知识

给出公式;

代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>//最大公约数long long gcd(long long a, long long b){long long c;if (a == 0){return b;}while (b != 0){c = b;b = a % b;a = c;}return a;}int main(){long long n;while (1){scanf("%lld", &n);if (n == 0){printf("0\n");continue;}if (n == -1){break;}int k;long long p[64];p[0] = 1;for (k = 0; k < n; ++ k){p[k + 1] = p[k] * 3;}long long cnt = n&1?n*p[n/2 +1]:(n/2)*(p[n/2] + p[n/2+1]);for (k = 1; k <= n; ++ k){cnt += p[gcd(k,n)];}cnt /= 2*n;printf("%lld\n",cnt);}return 0;}