40 lines
658 B
C++
40 lines
658 B
C++
#include <iostream>
|
|
using namespace std;
|
|
int gcd(int a,int b)
|
|
{
|
|
return b==0?a:gcd(b,a%b);
|
|
}
|
|
__int64 pow(int a,int b)
|
|
{
|
|
__int64 s=1;
|
|
for(int i=0;i<b;i++)
|
|
s*=a;
|
|
return s;
|
|
}
|
|
int main()
|
|
{
|
|
int n,i;
|
|
__int64 ans;
|
|
while(cin>>n)
|
|
{
|
|
ans=0;
|
|
if(n>=40)continue;
|
|
if(n<0)break;
|
|
if(n==0){ printf("0\n");continue; }
|
|
for(i=1;i<=n;i++)
|
|
ans+=pow(3,gcd(n,i));
|
|
if(n%2)
|
|
{
|
|
ans+=( pow(3,(n+1)/2) *n);
|
|
}
|
|
else
|
|
{
|
|
ans+=( pow(3,n/2+1) * n/2);
|
|
ans+=( pow(3,n/2) *n/2 );
|
|
}
|
|
ans/=(2*n);
|
|
printf("%I64d\n",ans);
|
|
}
|
|
return 0;
|
|
}
|