首页 > 代码库 > POJ 1286 Necklace of Beads(Polya简单应用)

POJ 1286 Necklace of Beads(Polya简单应用)

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