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;}