记录编号	363300	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]最小公倍数之和	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	8.560 s
提交时间	2017-01-11 06:31:43	内存使用	86.14 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define s1(n) ((long long)(n)%p*(((n)+1)%p)%p*inv_2%p)
#define s2(n) ((long long)(n)%p*(((n)+1)%p)%p*((((long long)(n)%p)<<1)%p+1)%p*inv_6%p)
using namespace std;
using namespace __gnu_pbds;
const int table_size=10000010,maxn=table_size+10,p=1000000007,inv_2=500000004,inv_6=166666668;
void get_table(int);
int S(long long);
bool notp[maxn]={false};
int prime[maxn]={0},phi[maxn]={0};
gp_hash_table<long long,int>hashmap;
long long n;
int main(){
	freopen("lcm.in","r",stdin);
	freopen("lcm.out","w",stdout);
	scanf("%lld",&n);
	get_table(min((long long)table_size,n));
	int ans=0;
	for(long long i=1,last;i<=n;i=last+1){
		last=n/(n/i);
		ans+=S(n/i)*((s1(last)-s1(i-1))%p)%p;
		ans%=p;
	}
	if(ans<0)ans+=p;
	printf("%d",ans);
	return 0;
}
void get_table(int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!notp[i]){
			prime[++prime[0]]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
			notp[i*prime[j]]=true;
			if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
			else{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
		}
	}
	for(int i=2;i<=n;i++){
		phi[i]=(long long)phi[i]*i%p*i%p;
		phi[i]=(phi[i]+phi[i-1])%p;
	}
}
int S(long long n){
	if(n<=table_size)return phi[n];
	else if(hashmap.find(n)!=hashmap.end())return hashmap[n];
	int ans=s1(n)*s1(n)%p;
	for(long long i=2,last;i<=n;i=last+1){
		last=n/(n/i);
		ans-=S(n/i)*((s2(last)-s2(i-1))%p)%p;
		ans%=p;
	}
	if(ans<0)ans+=p;
	return hashmap[n]=ans;
}
/*
h(i)=phi(d)*d^2
g(i)=sum{h(j)|1<=j<=i}
g(n)=sum{i^3|1<=i<=n}-sum{i^2*g(n/i)|2<=i<=n}
ans=sum{i*g(n/i)|1<=i<=n}
线筛预处理一部分g，大一些的部分直接上杜教筛即可
s_3(n)=s_1(n)^2,s_2(n)=n(n+1)(2n+1)/6
*/