解题思路:
数论函数(分块)+线性筛+推柿子
本题其实可以加多组测试数据目前复杂度是√n
公式如下
注意事项:
参考代码:
#include using namespace std; typedef long long ll; const int mod=1e9+7; const int N=1e7+10; ll mu[N]; int pri[N],num; bool st[N]; void init_pri(ll n){ mu[1]=1; st[1]=true; for(int i=2;i<=n;++i){ if(!st[i]){ pri[++num]=i; mu[i]=((1ll*i*i-1)%mod+mod)%mod; } for(int j=1;i*pri[j]<=n;++j){ st[i*pri[j]]=true; if(i%pri[j]==0){ mu[i*pri[j]]=1ll*mu[i]*pri[j]%mod*pri[j]%mod; break; } mu[i*pri[j]]=((1ll*mu[i]*mu[pri[j]])%mod+mod)%mod; } } for(int i=1;i<=n;++i){ mu[i]=((mu[i]+mu[i-1])%mod+mod)%mod; } } ll calc(ll n){ ll l=1,r; ll ans=0; for(;l<=n;l=r+1){ r=n/(n/l); ans=(ans+1ll*(mu[r]-mu[l-1])%mod*(n/l)%mod*(n/l)%mod)%mod; if(ans<0)ans+=mod; } return ans; } int main() { ll n; cin>>n; init_pri(n); cout<<calc(n)<<endl; }
0.0分
7 人评分
矩形面积交 (Java代码)浏览:1214 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:548 |
妹子杀手的故事 (C语言代码)浏览:1218 |
简单的a+b (C语言代码)浏览:598 |
printf基础练习2 (有点不明白)浏览:837 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:349 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1067 |
循环入门练习5 (C语言代码)浏览:836 |
1071题解浏览:487 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:530 |