记录编号	263964	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]最小公倍数之和	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	9.603 s
提交时间	2016-05-26 21:03:10	内存使用	61.20 MiB

#include<stdio.h>
#define HASH 1000007
#define mod 1000000007
#define ll long long
#define inv2 500000004
#define inv6 166666668
bool flag[5000010];
int p[500010];
ll ans,phi[5000010];
void pre(){
	phi[1]=1;
	for(int i=2;i<=5000000;++i){
		if(!flag[i])p[++p[0]]=i,phi[i]=i-1;
		for(int j=1;j<=p[0]&&i*p[j]<=5000000;++j){
			flag[i*p[j]]=1;
			if(!(i%p[j])){
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			phi[i*p[j]]=phi[i]*phi[p[j]];
		}
	}
	//++phi[1];
	for(int i=2;i<=5000000;++i){
		phi[i]=phi[i]*i%mod*i%mod;
		phi[i]+=phi[i-1];
		if(phi[i]>=mod)phi[i]-=mod;
	}
}
int shu,first[HASH];
struct edge{ll u,v;int nx;}o[HASH];
inline void add(ll u,ll v){
	int ha=u%HASH;
	o[++shu].u=u,o[shu].v=v,o[shu].nx=first[ha],first[ha]=shu;
}
inline ll sqr(ll n){
	return n%mod*((n+1)%mod)%mod*((n<<1|1)%mod)%mod*inv6%mod;
}
inline ll work(ll n){
	if(n<=5000000)return phi[n];
	int ha=n%HASH;
	for(int i=first[ha];i;i=o[i].nx)
		if(o[i].u==n)return o[i].v;
	ll ret=0;
	for(ll i=2,j;i<=n;i=j+1){
		j=n/(n/i);
		ret=(ret-(sqr(j)-sqr(i-1))%mod*work(n/i))%mod;
	}
	ll tmp=n%mod*((n+1)%mod)%mod*inv2%mod;
	tmp=tmp*tmp%mod;
	ret=(ret+tmp)%mod;
	if(ret<0)ret+=mod;
	add(n,ret);
	return ret;
}
int main(){
	freopen("lcm.in","r",stdin);
	freopen("lcm.out","w",stdout);
	pre();
	ll n,ans=0;scanf("%lld",&n);
	for(ll i=1,j;i<=n;i=j+1){
		j=n/(n/i);
		ans=(ans+work(n/i)*((i+j)%mod)%mod*((j-i+1)%mod)%mod*inv2)%mod;
	}
	printf("%lld",ans);
}