起源：
SGU 294 He’s Circle
遗憾的是，被吃了。
Poj有道类似的：

Mission

一个长度为组成，求有多少本质不同的环。

实际上，如果使用高精度，那么n可以到1e6级别

群

定义

一个集合。
并且满足：

封闭性

如果

结合律

如果

存在单位元

存在
那么的单位元。
类似于加法运算中的0，乘法运算中的1。

逆元

对于任意
其中是单位元。
那么的逆元。

不一定满足交换律

---

我们称呼包含阶群。

置换

置换相当于一个排列的一一映射。
例如：

是置换，而

就不是置换。

置换群

由置换组成的集合，运算是置换的连接。

置换的连接

例子：

---

正片开始

Burnside引理

已知一个n阶置换群；
求在其作用下有多少种本质不同的染色方案。

结论

其中个置换的作用下，
有多少个染色方案置换后不变。

Back to the Problem

一个长度为组成，求有多少本质不同的环。

---

我们考虑构造这样的n阶置换群：
每一种旋转都当作是一个置换，那么就有个置换，就构成个群。
例如，旋转

---

利用burnside引理，
我们可以先枚举出所有的染色方案，然后判断有多少种旋转可以使它旋转后不变。
但这显然是时间超限的。
我们需要进一步找出更好的性质。

Pólya计数法

循环

定义n阶循环是一种置换满足，

用循环表示旋转

题目中的，假设：
那么置换群就有，以下四种置换：

用旋转表示置换，通俗地，例如：

简单来讲就是，类似于环状的东西。
我们用

处于同一循环的珠子的颜色必须是相同的，才能使得置换后不变

旋转i个珠子对应的置换共有gcd(n,i)个循环，且其中每个循环的起始位置都依次相邻

裴蜀定理：ax+by=c，那么gcd(a,b)|c，其中a,b,x,y,c都是质数。