解题思路:
数论函数(分块)+线性筛+推柿子
本题其实可以加多组测试数据目前复杂度是√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 人评分
化学品问题 (C语言代码)浏览:1329 |
三进制小数 (C++代码)(第11位大于1.5才能进位)浏览:1140 |
C语言程序设计教程(第三版)课后习题8.4 (Java代码)浏览:728 |
printf基础练习2 (C语言代码)浏览:305 |
成绩转换 (C语言代码)浏览:1005 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:619 |
三角形 (C++代码)记忆化搜索浏览:1220 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:594 |
printf基础练习2 (C语言代码)浏览:746 |
【计算两点间的距离】 (C语言代码)浏览:1473 |