poj 2409 Let it Bead && poj 1286 Necklace of Beads（Polya定理）

题目:http://poj.org/problem?id=2409

题意：用k种不同的颜色给长度为n的项链染色

网上大神的题解：

1.旋转置换：一个有n个旋转置换，依次为旋转0,1,2，```n-1。对每一个旋转置换，它循环分解之后得到的循环因子个数为gcd(n,i).

2.翻转置换：分奇偶讨论。

奇数的时候翻转轴 = （顶点+对边终点的连线），一共有n个顶点，故有n个置换，且每个置换分解之后的因子个数为n/2+1;

偶数的时候翻转轴 = （顶点+顶点的连线），一共有n个顶点，故有n/2个置换，且每个置换分解之后的因子个数为n/2+1;

或者翻转轴 = （边终点+边中点的连线），一共有n个顶点，故有n/2个置换，且每个置换分解之后的因子个数为n/2;

 1 #include<stdio.h>
 2 #include<math.h>
 3 
 4 int gcd(int a,int b)
 5 {
 6     if(b)
 7        return gcd(b,a%b);
 8     else
 9        return a;
10 }
11 
12 double polya(double k,int n)
13 {
14     int i;
15 
16     double ans=0;
17     for(i=0;i<n;i++)
18        ans+=pow(k,gcd(n,i));
19     if(n%2)
20        ans+=n*pow(k,n/2+1);
21     else
22     {
23        ans+=(n/2)*pow(k,n/2+1);
24        ans+=(n/2)*pow(k,n/2);
25     }
26     return ans/(2*n);
27 }
28 int main()
29 {
30     int s;
31     double c;
32     while(scanf("%lf%d",&c,&s))
33     {
34        if(c==0||s==0)
35            break;
36        printf("%.0lf
",polya(c,s));
37     }
38     return 0;
39 }

题目：http://poj.org/problem?id=1286

题意：给你n颗珠子，将这n颗珠子围成一个圈形成一串项链，然后对每个珠子涂上红色、蓝色和绿色中的一种。

如果两种涂色方法可以通过旋转项链得到。那么这两种涂色方法视为一种。如果两种涂色方法可以通过一个对

称轴反映得到，那么这两种涂色方法也视为一种。问有多少种不同的涂色方法。

和2409一样的。。

 1 #include<stdio.h>
 2 #include<math.h>
 3 
 4 int gcd(int a,int b)
 5 {
 6     if(b)
 7        return gcd(b,a%b);
 8     else
 9        return a;
10 }
11 
12 int polya(int k,int n)
13 {
14     int i;
15 
16     double ans=0;
17     for(i=0;i<n;i++)
18        ans+=pow(k,gcd(n,i));
19     if(n%2)
20        ans+=n*pow(k,n/2+1);
21     else
22     {
23        ans+=(n/2)*pow(k,n/2+1);
24        ans+=(n/2)*pow(k,n/2);
25     }
26      return ans/(2*n);
27 }
28 int main()
29 {
30     int s;
31     double c;
32     while(~scanf("%d",&s)&&s!=-1)
33     {
34        c=3;
35        if(s<=0)
36        printf("0
");
37        else
38        printf("%d
",polya(c,s));
39     }
40     return 0;
41 }