非常裸的polya，只是我看polya看了非常久

吉大ACM模板里面也有

#include <cstdio>

#include <cmath>

#include <iostream>

using namespace std;

long long gcd(long long a,long long b)

{

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

}

int main()

{

    #ifndef ONLINE_JUDGE

		//freopen("G:/1.txt","r",stdin);

		//freopen("G:/2.txt","w",stdout);

	#endif

	long long p[33];

	p[0]=1;

	for(long long i=1;i<=24;i++)

	{

		p[i]=p[i-1]*3;

		//cout<<p[i]<<endl;

	}

	long long res=0;

	long long s;

	while(cin>>s)

	{

        if(s==-1)

            break;

        if(s==0)

        {

            cout<<"0\n";

            continue;

        }

		long long res=s&1?s*p[s/2+1]:(s/2)*(p[s/2]+p[s/2+1]);

		for(long long k=1;k<=s;k++)

		{

			res+=p[gcd(k,s)];

		}

		res/=2*s;

		cout<<res<<'\n';

	}

    return 0;

}