置换群---珠子染色

n个珠子绕成一个环，对每个珠子染色，有3种颜色可选。环旋转或者翻转后颜色模式相同的算同一种。
计算共有多少种不同的染色模式。

需用到polya定理:

PS.循环节个数查看方法：从上一排数看到下面的数

如：1 2 3 4 

       2  4 1 3

得1->2->4->3->1   即(1,2,3,4)长度为4  ，循环节个数为1

     

如：1 2 3 4 

       4 3 2 1 

得1->4->1  2->3->2 即(1,4) (2,3)，长度均为2，循环节个数为2

在该题中，有两种置换方式:


1.旋转置换。
对于旋转，所有的节点都会旋转，所以循环节长度应该是一样的，这个长度是多长呢？
设 每次转x格，现在在p号点，走k次后回到p点，即
p + kx≡p(%n)
== > kx = 0 (%n)
所以kx模n等于0，即kx是n的倍数。当然kx还是x的倍数，而k是循环节长度，要取最小,
则满足以上两个条件的最小的kx是lcm(x, n)。把lcm换成gcd:
kx = nx / gcd(n, x) == > k = n / gcd(n, x)

也就是说，循环节长度是n / gcd(x, n)  (走了这么多次)，意义是在每次转x格的前提下，n / gcd(x, n)个数

在来回交换。也就是每n / gcd(x, n)个数看为一组，n被分成好几组, 显然分成了gcd(x, n)个组,

所以对于旋转，循环节长度n / gcd(x, n), 循环节个数gcd(x, n)。

而每次可以转1步, 2步…n步,所以一共有n种置换

例：转3格

1 2 3 4 5 6

4 5 6 1 2 3

1->4->1   2->5->2   3->6->3   (1,4) (2,5) (3,6)长度为2，循环节个数为3

而n / gcd(x, n)=6/gcd(3,6)=2，即长度为2

   gcd(3,6) = 3 即循环节个数为3

转2格

1 2 3 4 5 6 7 8

7 8 1 2 3 4 5 6 

1->7->5->3->1   2->8->6->4->2  (1,7,5,3)  (2,8,6,4) 长度为4，循环节个数为2

再转2格

7 8 1 2 3 4 5 6 

5 6 7 8 1 2 3 4 

7->5->3->1->7   8->6->4->2->8  (7,5,3,1) (8,6,4,2) 长度为4,循环节为2

……………………………………

n / gcd(x, n)=8/gcd(2,8)=4，即长度为4

   gcd(2,8) = 2 即循环节个数为2

2.翻转置换, 根据 N 的奇偶性分情况讨论。
奇数：对称轴一定是经过一个点和它的对边，共有n个对称轴，假设对称轴是穿过n节点，
那么在对称中n + 1和n - 1互换，n + 2和n - 2互换，这样共有 (n - 1) / 2 + 1（对称轴穿过的点本身
是一个循环节）个循环节，n种置换。
偶数：
分情况讨论对称轴穿过两个点还是两条边。
两条边：n / 2个置换，每个置换的循环节个数都是 n / 2
两个点：n / 2个置换，每个置换循环节个数是 (n - 2) / 2 + 2 = n / 2 + 1
最后别忘了除以 | G |= n + n / 2 + n / 2 = 2 * n

带入polya定理公式能得到最终值

#include <iostream>
#include <cmath>
using namespace std;

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a%b);
}

int main()
{
	int n;
	cin >> n;//珠子个数
	int sum = 0;
	for (int i = 1;i <= n;i++)
		sum += (int)pow(3, gcd(n, i));//n个置换
	if (n % 2 == 0)//偶数的情况
	{
		sum += (n / 2)*pow(3, (n / 2));//两条边的情况 有n/种个情况
		sum += (n / 2)*pow(3, (n / 2) + 1);//两个点的情况 有n/2种情况
	}
	else//奇数的情况
	{
		sum += n*pow(3, (n - 1) / 2 + 1);
	}
	sum = sum / (2 * n);
	cout << sum << endl;
//	system("pause");
	return 0;
}