POJ 2049

题意：一串由n个珠子组成的项链，用c种颜色涂染，问能形成多少种不同项链。

限制：旋转得来的为同一种，翻转得来的也为同一种。

运用polya定理解题。

Polya定理

    设有n个对象，G是这n个对象上的置换群，用m种颜色涂染这n个对象，每个对象涂染一种颜色，问有多少种染色方案？一种染色方案在群G的作用下变为另一种方案，则这两种方案当作是一种方案。

针对本题分两种情况讨论：
旋转：
n种旋转方法每种旋转i个格（1<=i<=n）循环结有gcd（i，n）个
翻转：

（1）这种是经过某个顶点i与中心的连线为轴的翻转，由于n为偶数，有对称性，所以此种共n/2种翻转：

（2）这种是以顶点i和i+1的连线的中点与中心的连线为轴的翻转，同样，根据对称性，也有n/2种翻转：

所以给定长度n，共有2n种置换。

代码如下：

#include<iostream> 
#include<fstream> 
#include<cmath> 

using namespace std; 

int gcd(int s,int t){ 
    if(t==0) return s; 
    return gcd(t,s%t); 
} 
int m,n; 

void read(){ 
	//  ifstream cin("in.txt"); 
    int i,j,k; 
     long ans; 
    while(1){ 
        cin>>m>>n; 
        if(n==0&&m==0) 
            return; 
        ans=0; 
        for(i=0;i<n;i++) 
            ans+=pow(1.*m,gcd(n,i)); 
        if(n%2==0) 
            ans+=n/2*pow(1.*m,n/2)+n/2*pow(1.*m,n/2+1); 
        else
            ans+=n*pow(1.*m,n/2+1); 
        cout<<ans/n/2<<endl; 
    } 
	
} 

int main(){ 
    read(); 
    return 0; 
}