POJ 題目1286 Necklace of Beads（Polya定理）

Necklace of Beads Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 7061   Accepted: 2942

Description

Beads of red, blue or green colors are connected together into a circular necklace of n beads ( n < 24 ). If the repetitions that are produced by rotation around the center of the circular necklace or reflection to the axis of symmetry are all neglected, how many different forms of the necklace are there?
 

Input

The input has several lines, and each line contains the input data n.
-1 denotes the end of the input file.

Output

The output should contain the output data: Number of different forms, in each line correspondent to the input data.

Sample Input

4
5
-1

Sample Output

21
39

Source

Xi'an 2002

 

題目大意：

n個珠子串成一個圓，用三種顏色去塗色。問一共有多少種不同的塗色方法。

不同的塗色方法被定義為：如果這種塗色情況翻轉，旋轉不與其他情況相同就為不同。

 

解題思路：

Polya定理模版題。

對於順時針長度為i的旋轉，為pow(3,__gcd(n,i)；

對於翻轉，當為奇數時，有：n*pow(3.0,n/2+1);

當為偶數時，有：n/2*pow(3.0,n/2)+n/2*pow(3.0,n/2+1);

 

一共有2*n種情況，最後要除以2*n

ac代碼

 

#include
#include
#include
int gcd(int a,int b)
{
	if(a