Polya定理：
设G是一个p个对象的置换群，那么用k种颜色对p个对象进行染色！当一种方案在群G的作用下变为另外一种方案，那么我们这个时候就认为这两个方案是一样的。那么在这种规定下不同的染色方案为：
n=(Ek^m(f))/|G|，其中m(f)是置换f的循环节。
Polya定理是基于Burnside定理和另外一个定理的，其中Burnside定理的通俗表达方法如下：
1）如果令C(f)表示在置换f的作用下，本质不变的着色方案数！那么可以证明的是“本质不同的着色方案数就是所有置换f下的C(f)的平均数”。
在Burnside的基础上，我们在介绍一个定理：
2）如果使用k种颜色给有限集合S着色，那么对于一个置换f，在该置换下本质不变的着色方案数就是C(f)=k^(m(f))，其中m(f)是置换f的循环节数。
基于上面的1）2）两个定理，便很明显的得到Polya定理。
#include <cstdio> __int64 m[24]; void list() { m[0] = 1; for(int i = 1; i < 24; ++i) m[i] = m[i - 1]*3; } int gcd(int a,int b) { return b ? gcd(b,a%b):a; } int main() { int n; __int64 ans; list(); scanf("%d",&n); while(n != -1) { ans = 0; if(n == 0) { printf("%I64d\n",ans); scanf("%d",&n); continue; } for(int i = 1; i <= n; i++) ans += m[gcd(i,n)]; if(n % 2 == 0) ans += (m[n/2] + m[n/2 + 1])*n/2; else ans += n*m[(n + 1)/2]; printf("%I64d\n",ans/(n * 2)); scanf("%d",&n); } return 0; }