sb题写挂还有资格参加省选？
写挂10+次，莫名RE，简直崩溃
最后选择了抄hzwer的代码
这题是一个裸的欧拉函数
把原题中的式子拆一下就行了
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,ans=0;
long long phiQ(long long x)
{
long long t=x;
for(long long i=2;i*i<=n;i++)
if(x%i==0)
{
t=t/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)t=t/x*(x-1);
return t;
}
int main(){
freopen("2705.in","r",stdin);
freopen("2705.out","w",stdout);
scanf("%lld",&n);
for(long long i=1;i*i<=n;i++){
if(n%i==0){
ans+=(long long)i*phiQ(n/i);
if(i*i<n)ans+=(long long)(n/i)*phiQ(i);
}
}
printf("%lld\n",ans);
return 0;
}
评论 (0)
