记录编号	310031	评测结果	AAAAAATAAA
题目名称	[HZOI 2016]艾米利亚的求助	最终得分	90
用户昵称	Ezoi_Vermouth	是否通过	未通过
代码语言	C++	运行时间	4.125 s
提交时间	2016-09-21 10:33:20	内存使用	0.30 MiB

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<cmath> 
using namespace std;
const int maxn=1000;
long long cir=1;
long long a[maxn];long long b[maxn];long long tot;
long long n;
long long cccir[maxn];
long long flag;
long long ans;
void read()
{
	cin>>n;
}
long long pow_mod(long long a,long long i,long long n){
	if(i==0) return 1%n;
	long long temp=pow_mod(a,i>>1,n);
		temp=temp*temp%n;
	if(i&1) temp=temp*a%n;
	return temp;
}
bool test(long long n,long long a,long long d){
	if(n==2) return true;
	if(n==a) return true;
	if((n&1)==0) return false;
	while((d&1)==0) d=d>>1;
	long long t=pow_mod(a,d,n); 
	while((d!=n-1)&&(t!=1)&&(t!=n-1)){
		t=(t*t)%n;
		d=d<<1;
	} 
	if(t==n-1) return true;
	if((d&1)==1) return true;
}
bool isprime(long long n){
	if(n<2) return false;
	int a[]={2, 3, 7, 61, 24251};
	for(int i=0;i<=4;i++)	if(!test(n,a[i],n-1)) return false;
	return true;
} 
long long phi(long long x)
{
	long long res=x,k=sqrt(x);
	for(int i=2;i<=k;++i){
		if(x%i==0){
			res-=res/i;
			while(x%i==0)x/=i;
		}
	}
	if(x>1)res-=res/x;
	return res;
}
long long solve(long long n)
{
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b)); 
	long long temp,i,now;
	cir=1;
	temp=(long long)((double)sqrt(n)+1);
	tot=0;
	now=n;
	for(i=2;i<=temp;++i)if(now%i==0)
	{
		a[++tot]=i;
		b[tot]=0;
		while(now%i==0)
		{
			++b[tot];
			now/=i;
		}
	}
	if(now!=1)
	{
		a[++tot]=now;
		b[tot]=1;
	}
	for(int i=1;i<=tot;++i)
	cir*=b[i]+1;
	return cir;
}
int main()
{
	freopen("aimiliyadehelp.in","r",stdin);
	freopen("aimiliyadehelp.out","w",stdout);
	read();
	if(isprime(n)) {cout<<"21312321";return 0;}
	int o=sqrt(n);
	for(int i=1;i<=o;++i)
	{
		if(n%i==0)
		{
			cccir[++flag]=i;
			if(i*i!=n) cccir[++flag]=n/i;
			
		} 
	}
	for(int i=2;i<=flag;++i)
	ans+=phi(n/cccir[i])*solve(cccir[i]); 
	cout<<ans;
	return 0;
}