POJ 1286 Necklace of Beads

Problem Description:
Three colors of beads are available.
Count the number of different circular necklace that could be formed.
Two necklaces are identical iff after some rotation or flip, each position has the same color of bead.

Constraints:

Solution:
Let us calculate with Polya's.
First we know that k-rotation has groups, meaning that k-rotation contributes number of combinations.
Then consider flipping:
when N is odd:
Choose a bead, make a line with it and the center of the circle, make both sides to the line symetric => ways to choose, each combinations.
Choose a bead, make a line with it and the center of the circle (also to a bead at the other side), make both sides to the line symetric => ways to choose, each combinations.
Or, choose two beads and cut in the middle, through the center of the circle.

Code:

#include <iostream>
#include <algorithm>

const int MAXN = 24;

unsigned long long ans[MAXN];

unsigned long long int_pow(unsigned long long v, int p) {
  unsigned long long res = 1;
  for (int i = p; i; i >>= 1) {
    if (i & 1) res *= v;
    v *= v;
  }
  return res;
}

unsigned long long solve(int n) {
  if (n == 0 || ans[n]) return ans[n];
  for (int i = 1; i <= n; ++i) {
    ans[n] += int_pow(3, std::__gcd(i, n));
  }
  if (n & 1) {
    ans[n] += int_pow(3, n / 2 + 1) * n;
  } else {
    ans[n] += int_pow(3, n / 2 + 1) * (n / 2);
    ans[n] += int_pow(3, n / 2) * (n / 2);
  }
  return ans[n] /= n * 2;
}

signed main() {
  std::ios::sync_with_stdio(false);
  int n;
  while (std::cin >> n && ~n) {
    std::cout << solve(n) << std::endl;
  }
  return 0;
}