POJ.2409 Let it Bead

1.Problem
http://poj.org/problem?id=2409

2.Idea
Polya's theorem.

3.Source

 int gcd(int a, int b)  
 {  
      return b == 0 ? a : gcd(b, a%b);  
 }  
 int power(int p, int n)  
 {  
      int ans = 1;  
      while (n)  
      {  
           if (n & 1)  
                ans *= p;  
           p *= p;  
           n /= 2;  
      }  
      return ans;  
 }  
 void solve()  
 {  
      while (1) {  
           int c, s, ans = 0;  
           cin >> c >> s;  
           if (c == 0 && s == 0) break;  
           for (int i = 1; i <= s; i++)  
                ans += power(c, gcd(s, i));  
           if (s & 1)   
                ans += s*power(c, s / 2 + 1);  
           else  
                ans += (power(c, s / 2 + 1) + power(c, s / 2))*(s / 2);  
           ans /= 2 * s;  
           cout << ans << endl;  
      }  
 }