POJ 2409 Let it Bead（Polya简单应用）

 1 /*************************************************************************
 2     > File Name: POJ2409.cpp
 3     > Author: GLSilence
 4     > Created Time: 2014年07月29日 星期二 22时56分58秒
 5  ************************************************************************/
 6 
 7 #include<stdio.h>
 8 #include<iostream>
 9 #include <math.h>
10 using namespace std;
11 
12 #define LL long long
13 
14 LL GCD(LL a, LL b){
15     return b ? GCD(b, a%b) : a;
16 }
17 
18 int n, m;
19 
20 int main()
21 {
22     while(~scanf("%d%d", &m, &n) && (n||m)){
23         LL ans = 0;
24         
25         for(int i = 1; i <= n; ++i){
26             ans += (LL)pow(m*1.0, GCD(n, i));
27         }
28 
29         if(n%2){
30             ans += n*(LL)pow(m*1.0, n/2+1);
31         }
32         else {
33             ans += n/2*(LL)pow(m*1.0, n/2);
34             ans += n/2*(LL)pow(m*1.0, n/2+1);
35         }
36 
37         printf("%lld\n", ans/2/n);
38 
39     }
40 
41     return 0;
42 }