比赛 |
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;
}