12
25
2015
0

[bzoj]2226: [Spoj 5971] LCMSum

-->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...

Category: bzoj | Tags: gcd 数论 | Read Count: 901

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com