解题思路:
数论函数(分块)+线性筛+推柿子
本题其实可以加多组测试数据目前复杂度是√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语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:967 |
九宫重排 (C++代码)浏览:2160 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1022 |
程序员的表白 (C语言代码)浏览:656 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:1030 |
WU-陶陶摘苹果2 (C++代码)浏览:970 |
矩阵加法 (C语言代码)浏览:1720 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:614 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:526 |
C二级辅导-统计字符 (C语言描述——用函数求解)浏览:1178 |