记录编号	263800	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]最小公倍数之和	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	7.735 s
提交时间	2016-05-26 17:20:20	内存使用	52.13 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int mod=1e9+7;
const int MOD=1333331;
LL n,inv2,inv6;
bool vis[5000010];
int p[500010],cnt=0;
LL phi[5000010];

struct HASHMAP{
	int h[MOD+10],cnt;
	int next[100010];
	LL S[100010],st[100010];
	LL ask(LL k){
		int key=k%MOD;
		for(int i=h[key];i;i=next[i]){
			if(S[i]==k)return st[i];
		}return -1;
	}
	void push(LL k,LL v){
		int key=k%MOD;
		++cnt;next[cnt]=h[key];h[key]=cnt;
		S[cnt]=k;st[cnt]=v;
	}
}H;
void Get_Prime(){
	phi[1]=1;
	for(int i=2;i<=5000000;++i){
		if(!vis[i]){
			p[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt;++j){
			if(1LL*i*p[j]>5000000)break;
			int ip=i*p[j];
			vis[ip]=true;
			if(i%p[j]==0){
				phi[ip]=phi[i]*p[j];
				break;
			}phi[ip]=phi[i]*(p[j]-1);
		}
	}
	for(int i=2;i<=5000000;++i){
		phi[i]=phi[i]*i%mod*i+phi[i-1];
		phi[i]%=mod;
	}return;
}
LL pow_mod(LL v,LL p){
	LL tmp=1;
	while(p){
		if(p&1)tmp=tmp*v%mod;
		v=v*v%mod;p>>=1;
	}return tmp;
}
LL Get_mod(LL v){return v%mod;}
LL S(LL n){
	if(n<=5000000)return phi[n];
	LL tmp=H.ask(n);
	if(tmp!=-1)return tmp;
	LL la,A=Get_mod(n);
	A=A*(A+1)%mod*inv2%mod;
	A=A*A%mod;
	for(LL i=2;i<=n;i=la+1){
		LL now=n/i;
		la=n/now;
		LL t1=Get_mod(la),t2=Get_mod(i-1);
		t1=t1*(t1+1)%mod*((t1<<1)|1)%mod*inv6;
		t2=t2*(t2+1)%mod*((t2<<1)|1)%mod*inv6;
		t1=t1-t2;t1%=mod;if(t1<0)t1+=mod;
		A=A-t1*S(now)%mod;
		if(A<0)A+=mod;
	}H.push(n,A);
	return A;
	
}
int main(){
	freopen("lcm.in","r",stdin);
	freopen("lcm.out","w",stdout);
	scanf("%lld",&n);
	Get_Prime();
	LL la,ans=0;
	inv2=pow_mod(2LL,mod-2);
	inv6=pow_mod(6LL,mod-2);
	for(LL i=1;i<=n;i=la+1){
		LL now=n/i;
		la=n/now;
		ans=ans+Get_mod(i+la)*Get_mod(la-i+1)%mod*inv2%mod*S(now);
		ans%=mod;
	}printf("%lld\n",ans);
	return 0;
}