POJ 1286 Necklace of Beads（Polya简单应用）

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

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

 1 /*************************************************************************
 2     > File Name: POJ1286.cpp
 3     > Author: GLSilence
 4     > Created Time: 2014年07月29日 星期二 22时05分01秒
 5  ************************************************************************/
 6 
 7 #include<stdio.h>
 8 #include<iostream>
 9 #include <math.h>
10 #define LL long long
11 using namespace std;
12 
13 LL GCD(LL a, LL b){
14     return (b)?(GCD(b, a%b)):a;
15 }
16 
17 int n;
18 
19 int main()
20 {
21     while(~scanf("%d", &n) && n!=-1){
22         if(n == 0){
23             printf("0
");
24             continue;
25         }
26         LL ans = 0;
27         
28         for(int i = 1; i <= n; ++i){
29             ans += (LL)pow(3.0, GCD(n, i));
30         }
31 
32 
33         if(n%2){
34             ans += n*(LL)pow(3.0, n/2+1);
35         }
36         else {
37             ans += n/2*(LL)pow(3.0, n/2);
38             ans += n/2*(LL)pow(3.0, n/2+1);
39         }
40         printf("%lld
", ans/2/n);
41     }
42 
43     return 0;
44 }

POJ 1286