poj2409&&poj1286

题目意思：都是给定m个颜色，然后去个长度为N的项链染色，无其他限制。

然后反转，顺时针旋转算是一种方案啊

思路:比较基础的polya题目，算是模板题吧。。

1）旋转将项链旋转i格，循环个数为gcd（N，i）

2）反转：

A.n为奇数时，共有 n个循环节数为（n+1）/2的循环群

B、n为偶数，可以根据一条边及一个点对称，有n/2 个循环节数为（n+2）/2的循环群

还可以根据两个点对称，有n/2个循环节数为n/2的循环群

code：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <algorithm>
 7 
 8 typedef __int64 LL;
 9 using namespace std;
10 __int64 n, m, gcd[30][30];
11 
12 void init(){
13   for (int i = 1;i <= 24; ++i)   
14     for (int j = 1; j <= 24; ++
15     j) 
16       for (int k = 1; k <= min(i,j); ++k)
17        if (j % k == 0 && i % k ==0) gcd[i][j] = k;
18      
19 }
20 
21 void solve(){
22     LL sum = 0; 
23     if (n == 0){
24           printf("%d\n", 0);
25           return ;
26     }
27     for (int i = 1; i <= n;  ++i)
28             sum += (LL)( pow( m * 1.0, gcd[i][n] * 1.0));
29     if (n&1){
30           sum += (LL)( n* pow(m * 1.0, (n  + 1)/ 2.0));
31     } else {
32           sum += (LL)((n / 2) *  pow(m *1.0, (n + 2) / 2 * 1.0));
33           sum += (LL)((n / 2) *  pow(m *1.0, n / 2 * 1.0));
34     }
35     printf("%lld\n", sum / (2 * n));
36     
37 }
38 
39 int main(){
40      freopen("poj1286.in", "r", stdin);
41      freopen("poj1286.out","w", stdout);
42      init();
43      m = 3;
44      while (scanf("%lld", &n) != EOF && n != -1)
45         solve();
46 }

code2：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <algorithm>
 7 
 8 typedef __int64 LL;
 9 using namespace std;
10 __int64 n, m, gcd[34][34];
11 
12 void init(){
13   for (int i = 1;i <= 33; ++i)   
14     for (int j = 1; j <= 33; ++
15     j) 
16       for (int k = 1; k <= min(i,j); ++k)
17        if (j % k == 0 && i % k ==0) gcd[i][j] = k;
18      
19 }
20 
21 void solve(){
22     LL sum = 0; 
23     if (n == 0){
24           printf("%d\n", 0);
25           return ;
26     }
27     for (int i = 1; i <= n;  ++i)
28             sum += (LL)( pow( m * 1.0, gcd[i][n] * 1.0));
29     if (n&1){
30           sum += (LL)( n* pow(m * 1.0, (n  + 1)/ 2.0));
31     } else {
32           sum += (LL)((n / 2) *  pow(m *1.0, (n + 2) / 2 * 1.0));
33           sum += (LL)((n / 2) *  pow(m *1.0, n / 2 * 1.0));
34     }
35     printf("%I64d\n", sum / (2 * n));
36     
37 }
38 
39 int main(){
40      freopen("poj2409.in", "r", stdin);
41      freopen("poj2409.out","w", stdout);
42      init();
43      while (scanf("%I64d%I64d", &m, &n) != EOF && n != 0 && m != 0)
44         solve();
45 }