记录编号	219728	评测结果	AAAAAAAAAA
题目名称	[SGU U294]他的圆圈	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	11.225 s
提交时间	2016-01-15 19:50:36	内存使用	15.08 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
const int SIZEN=9000;
typedef long long LL;
const LL MOD=1000000000;
int N;
LL B[SIZEN]={0};
int mp[200010]={0};;
class miku
{
	public:
	int n;
	LL A[SIZEN];
	miku()
	{
		n=0;
		memset(A,0,sizeof(A));
	}
	void operator =(int x)
	{
		//memset(A,0,sizeof(A));
		while(n>1) A[--n]=0;
		n=1;
		A[0]=x;
	}
	void operator *=(miku x)
	{
		int p=n+x.n+1;
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=x.n;j++)
			{
				B[i+j]+=A[i]*x.A[j];
				B[i+j+1]+=B[i+j]/MOD;
				B[i+j]%=MOD;
			}
		}
		n=p;
		for(int i=0;i<=n;i++) A[i]=B[i],B[i]=0;
		while(n>1&&A[n-1]==0) n--;
	}
	void operator +=(miku c)
	{
		n=max(n,c.n)+1;
		for(int i=0;i<=min(n,c.n);i++)
		{
			A[i]+=c.A[i];
			A[i+1]+=A[i]/MOD;
			A[i]%=MOD;
		}
		while(n>1&&A[n-1]==0) n--;
	}
	void operator /=(LL x)
	{
		for(int i=n-1;i>=0;i--) 
		{
			if(i>0) A[i-1]+=(A[i]%x)*MOD;
			A[i]/=x;
		}
		while(n>1&&A[n-1]==0) n--;
	}
	void print()
	{
		printf("%d",A[n-1]);
		for(int i=n-2;i>=0;i--) printf("%09d",A[i]);
		printf("\n");
	}
}P[200];
miku ans;
void read()
{
	scanf("%d",&N);
}
int gcd(LL x,LL y)
{
	if(y==0) return x;
	return gcd(y,x%y);
}
miku re,tem;
miku qpow(int x,int y)
{
	re=0;tem=0;
	tem=x;
	re=1;
	while(y>0)
	{
		if(y&1) re*=tem;tem*=tem;y>>=1;
	}
	return re;
}
void work()
{
	ans=0;
	ans=qpow(2,N);
	int k=0;
	for(int i=1;i<N;i++)
	{
		//p=qpow(2,gcd(i,N));
		if(mp[gcd(i,N)]==0)
		{
			mp[gcd(i,N)]=++k;
			P[k]=qpow(2,gcd(i,N));
		}
		ans+=P[mp[gcd(i,N)]];
		//cout<<ans.n<<endl;
	}
	//cout<<k<<endl;
	ans/=N;
	//cout<<ans.n<<endl;
	ans.print();
}
int main()
{
	freopen("Hescircle.in","r",stdin);
	freopen("Hescircle.out","w",stdout);
	read();
	work();
	return 0;
}