记录编号	403045	评测结果	AAAAAAAAAA
题目名称	[SGU U294]他的圆圈	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.246 s
提交时间	2017-05-08 22:03:59	内存使用	6.78 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=2e5+10,bit=4e4;
int n,phi[N],p[N],cnt;
bool isp[N];
const int base=1e5;
struct big{
	int n;ll a[bit];
	big(int x=0){
		n=0;
		memset(a,0,sizeof a);
		for (;x;x/=base) a[n++]=x%base;
	}
	void getmod(){
		for (int i=0;i<n-1;i++)
			a[i+1]+=a[i]/base,a[i]%=base;
		int q=n-1;
		while (q>=0&&!a[q]) n--,q--;
	}
	void operator *= (const big &x){
		static big ans(0);
		ans.n=n+x.n;
		for (int i=0;i<ans.n;i++) ans.a[i]=0;
		for (int i=0;i<n;i++)
		for (int j=0;j<x.n;j++)
			ans.a[i+j]+=a[i]*x.a[j];
		ans.getmod();
		*this=ans;
	}
	void operator += (const big &x){
		static big ans(0);
		ans.n=max(n,x.n)+1;
		for (int i=0;i<ans.n;i++) ans.a[i]=0;
		for (int i=0;i<n;i++) ans.a[i]=a[i];
		for (int i=0;i<x.n;i++) ans.a[i]+=x.a[i];
		ans.getmod();
		*this=ans;
	}
};
typedef long double db;
const db pi=acos(-1.0);
struct cp{
	db x,y;
	cp(db X=0,db Y=0){x=X;y=Y;}
	cp operator + (cp &a)const{return cp(x+a.x,y+a.y);}
	cp operator - (cp &a)const{return cp(x-a.x,y-a.y);}
	cp operator * (cp &a)const{return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
}w[bit],iw[bit],a[bit],b[bit];
void init(int n){
	db alpha=2*pi/n;
	w[0]=cp(1,0);w[1]=cp(cos(alpha),sin(alpha));
	for (int i=2;i<=n;i++) w[i]=w[i-1]*w[1];
	for (int i=0;i<=n;i++) iw[i]=w[n-i]; 
}
void fft(int n,cp *a,cp *w){
	for (int i=0,j=0;i<n;i++){
		if (i<j) swap(a[i],a[j]);
		for (int k=n>>1;(j^=k)<k;k>>=1);
	}
	for (int i=2;i<=n;i<<=1){
		int m=i>>1,step=n/i;
		for (int j=0;j<n;j+=i)
		for (int k=0;k<m;k++){
			cp t=a[j+k+m]*w[k*step];
			a[j+k+m]=a[j+k]-t;
			a[j+k]=a[j+k]+t;
		}
	}
}
void multify(big &x,big &y){
	int size=1;
	while (size<x.n+y.n) size<<=1;
	init(size);
	for (int i=0;i<size;i++) a[i]=x.a[i];
	for (int i=0;i<size;i++) b[i]=y.a[i];
	fft(size,a,w);fft(size,b,w);
	for (int i=0;i<size;i++) a[i]=a[i]*b[i];
	fft(size,a,iw);
	for (int i=0;i<size;i++) x.a[i]=ll(a[i].x/size+0.5);
	x.n+=y.n;
	x.getmod();
}
#define FFT
big power(int x,int y){
	big ans(1),X(x);
	for (;y;y>>=1){
		if (y&1)
		#ifndef FFT
		ans*=X;
		#else
		multify(ans,X);
		#endif
		#ifndef FFT
		X*=X;
		#else
		multify(X,X);
		#endif
	}
	return ans;
}
int main()
{
	freopen("Hescircle.in","r",stdin);
	#ifndef FFT
	freopen("Hescircle.ans","w",stdout);
	#else
	freopen("Hescircle.out","w",stdout);
	#endif
	scanf("%d",&n);
	phi[1]=1;
	for (int i=2;i<=n;i++){
		if (!isp[i]) p[++cnt]=i,phi[i]=i-1;
		for (int j=1;j<=cnt&&i*p[j]<=n;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) phi[x]=phi[i]*phi[p[j]];
			else{phi[x]=phi[i]*p[j];break;}
		}
	}
	big ans(0);
	for (int d=1;d<=n;d++)
	if (!(n%d)){
		big x(phi[n/d]),y=power(2,d);
		#ifndef FFT 
		x*=y;
		#else
		multify(x,y);
		#endif
		ans+=x;
	}
	ll now=0;
	for (int i=ans.n-1;i>=0;i--){
		now=now*base+ans.a[i];
		ans.a[i]=now/n;
		now%=n;
	}
	int p=ans.n-1;
	for (;p&&!ans.a[p];p--);
	printf("%lld",ans.a[p--]);
	for (;p>=0;printf("%05lld",ans.a[p--]));
	puts("");
	return 0;
}