同poj 2409
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
long long c=3,n;
while(cin>>n)
{
long long ans=0;
if(n==-1)
break;
if(n<=0)
{
cout<<"0"<<endl;
continue;
}
for(int i=1;i<=n;i++)
ans+=pow(c*1.0,gcd(n,i)*1.0);//原来加了个（int）
if(n%2==1)
{
ans+=n*pow(c*1.0,(n+1)/2.0);
}
else
{
ans+=(n/2)*pow(c*1.0,n/2.0)+(n/2)*pow(c*1.0,n/2.0+1);
}
ans/=(n*2);
cout<<ans<<endl;
}
//system("pause");
return 0;
}