http://poj.org/problem?id=1286
// File Name: poj1286.cpp
// Author: bo_jwolf
// Created Time: 2013年10月07日 星期一 21:31:08 #include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime> #define INT long long int using namespace std;
INT gcd( INT a, INT b){
return b == 0? a: gcd( b, a % b );
} INT c = 3, s;
INT polya(){
INT ans = 0;
for( INT i = 0; i < s; ++i ){
ans += (INT)pow( 1.0 * c, gcd( s, i ) );
}
if( s % 2 ){
ans += s * ( INT )pow( 1.0 * c, ( s / 2 + 1 ) );
}
else{
ans += s / 2 * ( INT )pow( 1.0 * c, s / 2 );
ans += s / 2 * ( INT )pow( 1.0 * c, s / 2 + 1 );
}
return ans / 2 / s;
} int main(){
INT ans;
while( scanf( "%lld", &s ) != EOF ){
if( s == -1 )
break;
if( s == 0 )
ans = 0;
else
ans = polya();
printf( "%lld\n", ans );
}
return 0;
}