Peking University Online Judge 1286 Necklace of Beads

テストケースに0を忍ばせるとかいうアレ
ポリアの数え上げ定理を使いましたが、反転のパートは想像で書きました（バカなの？）

#include<cstdio>
#include<vector>
using namespace std;
typedef long long int ll;

int n;
vector<ll> va;

int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int main(){
	for(int i = 0; i <= 24; i++){
		if(i == 0) va.push_back(1LL);
		else va.push_back(va.back() * 3LL);
	}
	for(;;){
		scanf("%d", &n);
		if(n == -1) break;
		if(n == 0){
			printf("0\n");
			continue;
		}
		ll res = 0;
		for(int i = 1; i <= n; i++){
			if(i == 1 || i == n){
				res += va[n / i];
			}else if(gcd(n, i) != 1){
				res += va[gcd(n, i)];
			}else{
				res += 3;
			}
		}
		for(int i = 1; i <= n; i++){
			if(n % 2 == 0){
				if(i % 2 == 0){
					res += va[n / 2];
				}else{
					res += va[(n - 2) / 2 + 2];
				}
			}else{
				res += va[(n - 1) / 2 + 1];
			}
		}
		printf("%lld\n", res / (ll)(n * 2));
	}
	return 0;
}