題目鏈接

https://lydsy.com/JudgeOnline/problem.php?id=4916

題解

∑i=1Nμ(i2)=1∑i=1Nφ(i2)=∑i=1Niφ(i) \sum_{i=1}^N \mu(i^2)=1\\ \sum_{i=1}^N \varphi(i^2)=\sum_{i=1}^N i\varphi(i) i=1∑N?μ(i2)=1i=1∑N?φ(i2)=i=1∑N?iφ(i)

直接杜教篩即可。

代碼

#include <map> #include <cstdio>int read() {int x=0,f=1;char ch=getchar();while((ch<'0')||(ch>'9')){if(ch=='-'){f=-f;}ch=getchar();}while((ch>='0')&&(ch<='9')){x=x*10+ch-'0';ch=getchar();}return x*f; }const int maxn=1000000; const int mod=1000000007; const int inv6=166666668;int p[maxn+10],prime[maxn+10],cnt,f[maxn+10];int getprime() {p[1]=f[1]=1;for(int i=2; i<=maxn; ++i){if(!p[i]){prime[++cnt]=i;f[i]=i-1;}for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j){int x=i*prime[j];p[x]=1;if(i%prime[j]==0){f[x]=f[i]*prime[j];break;}f[x]=f[i]*(prime[j]-1);}}for(int i=1; i<=maxn; ++i){f[i]=(f[i-1]+1ll*f[i]*i)%mod;}return 0; }std::map<int,int> mp;int getsum(int n) {if(n<=maxn){return f[n];}if(mp.count(n)){return mp[n];}int ans=1ll*n*(n+1)%mod*(2*n+1)%mod*inv6%mod;for(int l=2,r; l<=n; l=r+1){r=n/(n/l);ans=(ans-((1ll*r*(r+1)/2)-(1ll*(l-1)*l)/2)%mod*getsum(n/l))%mod;if(ans<0){ans+=mod;}}return mp[n]=ans; }int n;int main() {getprime();n=read();printf("1\n%d\n",getsum(n));return 0; }

轉載于:https://www.cnblogs.com/Canopus-wym/p/10376064.html

總結

以上是生活随笔為你收集整理的BZOJ 4916 神犇和蒟蒻的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。