-->http://www.lydsy.com/JudgeOnline/problem.php?id=2226
跟比利做题时不时就会出现这种我还没做过的题$0.0$
$O(T\sqrt n)$
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
#define ll long long
int i,j,k,m,n,x,y,T,phi[N],o;ll ans;
int main(){
phi[1]=1;
for(i=2;i<=N;++i)if(!phi[i])for(j=i;j<=N;j+=i){
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
for(ans=0,T=read();T--;){
for(ans=0,n=read(),o=sqrt(n),i=1;i<=o;++i)if(n%i==0){
if(i!=1)ans+=1ll*i*phi[i]/2;
else ans+=1;
if(i*i!=n)ans+=1ll*n/i*phi[n/i]/2;
}
printf("%lld\n",1ll*ans*n);
}
}
loading...
评论 (0)
