比赛 20190522数学 评测结果 AAAAAEEEWE
题目名称 最小公倍数之和 最终得分 50
用户昵称 梦那边的美好ET 运行时间 1.434 s
代码语言 C++ 内存使用 166.25 MiB
提交时间 2019-05-23 08:21:04
显示代码纯文本
#include<bits/stdc++.h>
#define LL long long
#define maxn 10000010
using namespace std;
const LL mod=(LL)1000000007;
int p[maxn],bk[maxn],lp,n;
LL ans,f[maxn];
int main(){
	freopen("lcm.in","r",stdin);
	freopen("lcm.out","w",stdout);
	f[1]=(LL)1;scanf("%d",&n);
	for(int i=2;i<=max(10,n);i++){
		if(bk[i]==0)p[++lp]=i,f[i]=(LL)(i-1);
		for(int j=1;j<=lp&&p[j]*i<=max(n,10);j++){
			bk[p[j]*i]=1;
			if(i%p[j]==0){f[i*p[j]]=(LL)p[j]*f[i]%mod;break;}
			f[p[j]*i]=f[i]*(LL)(p[j]-1)%mod;
		}
	}
	for(int i=2;i<=max(10,n);i++)f[i]=(f[i-1]+f[i]*(LL)i%mod*(LL)i)%mod;
	for(int i=1;i<=n;i++)ans=(ans+(LL)i*f[n/i])%mod;
	printf("%lld\n",ans);
	return 0;
}