Necklace of Beads

大意:3种颜色的珠子，n个串在一起，旋转变换跟反转变换如果相同就算是同一种，问会有多少种不同的组合。

思路：正规学Polya的第一道题，在楠神的带领下，理解的还算挺快的，代码没什么好说的，裸的Polya，也不需要优化。

/*************************************************************************
    > File Name: POJ1286.cpp
    > Author: GLSilence
    > Created Time: 2014年07月29日 星期二 22时05分01秒
 ************************************************************************/

#include<stdio.h>
#include<iostream>
#include <math.h>
#define LL long long
using namespace std;

LL GCD(LL a, LL b){
    return (b)?(GCD(b, a%b)):a;
}

int n;

int main()
{
    while(~scanf("%d", &n) && n!=-1){
        if(n == 0){
            printf("0\n");
            continue;
        }
        LL ans = 0;
        
        for(int i = 1; i <= n; ++i){
            ans += (LL)pow(3.0, GCD(n, i));
        }


        if(n%2){
            ans += n*(LL)pow(3.0, n/2+1);
        }
        else {
            ans += n/2*(LL)pow(3.0, n/2);
            ans += n/2*(LL)pow(3.0, n/2+1);
        }
        printf("%lld\n", ans/2/n);
    }

    return 0;
}