题目链接

题解

$\sum_{i=1}^N \mu(i^2)=1\\ \sum_{i=1}^N \varphi(i^2)=\sum_{i=1}^N i\varphi(i)$

直接杜教筛即可。

代码

#include #include 
    
     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
     
       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://blog.csdn.net/wang3312362136/article/details/86062481 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：一个多项式求逆的卡常技巧

下一篇：BZOJ 4816 [Sdoi2017]数字表格

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

题解

代码

发表评论

最新留言

关于作者

推荐文章