POJ 1286 Necklace of Beads Ploya定理
来源：http://poj.org/problem?id=1286
题意：用三种颜色着色一个长度为n的项链，问有多少种方法。。。
思路：继续裸的Ploya，水水更健康。。。被n=0坑了一次re，被long long坑了一次wa，，，
代码：
#include <iostream>#include <cstdio>#include <string.h>using namespace std;typedef long long ll;int gcd(int a,int b){if(b == 0)return a;return gcd(b,a%b);}ll mi(int x){ll s = 1;for(int i = 1;i <= x;++i)s *= 3;return s;}int main(){int n;while(scanf("%d",&n) != EOF){ if(n == -1) break; if(n == 0){ printf("0\n");continue; } ll sum = 0; for(int i = 1;i <= n;++i){ int x = gcd(n,i);sum += mi(x); } if(n % 2) sum += ( n * mi( (n-1)/2 + 1 ) ); else sum += ( n/2 * mi( n/2 ) + n/2 * mi( n/2 + 1 )); printf("%lld\n",sum / (2*n));}return 0;}