POJ 1286 Necklace of Beads ——Burnside

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define F(i,j,k) for (int i=j;i<=k;++i)

ll f[25],pow[30];
int n;

int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);}

int main()
{
	f[0]=0;pow[0]=1;
	F(i,1,23) pow[i]=pow[i-1]*3;
	F(z,1,23)
	{
		F(i,0,z-1) f[z]+=pow[gcd(i,z)];
		if (z&1) f[z]+=z*pow[z/2+1];
		else f[z]+=z/2*pow[z/2],f[z]+=z/2*pow[z/2+1];
		f[z]/=2*z;
	}
	while (scanf("%d",&n)&&n>=0)
		printf("%lld\n",f[n]);
}