POJ.1286 Necklace of Beads

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

2.Idea
Polya's theorem.

3.Source

 Int p[110], ans, n;  
 Int gcd(Int a, Int b)  
 {  
      if (!(a%b)) return b;  
      return gcd(b, a%b);  
 }  
 void solve()  
 {  
      int i, j;  
      while (1) {  
           cin >> n;  
           if (n == 0) {  
                cout << 0 << endl;  
                continue;  
           }  
           if (n == -1) return;  
           p[0] = 1;  
           for (int i = 0; i < n; i++) p[i + 1] = p[i] * 3;  
           if (!(n % 2)) ans = (n / 2) * (p[n / 2 + 1] + p[n / 2]);  
           else ans = n * p[n / 2 + 1];  
           for (int i = 1; i <= n; i++) ans += p[gcd(i, n)];  
           ans /= 2 * n;  
           cout << ans << endl;  
      }  
 }