1968: [Ahoi2005]COMMON 约数研究

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

 #include<cstdio>

 #include<iostream>

 #define M 1000008

 using namespace std;

 long long tot,f[M],sum[M],ans,n,b[M],p[M];

 int main()

 {

     scanf("%d",&n);

     ans=;

     for(int i=;i<=n;i++)

       {

         if(!b[i])

           {

             tot++;

             p[tot]=i;

             sum[i]=;

             f[i]=;

           }

         for(int j=;j<=tot;j++)

           {

             if(i*p[j]>n)

               break;

             b[i*p[j]]=;

             if(i%p[j])

               {

                 f[i*p[j]]=f[i]*;

                 sum[i*p[j]]=;

               }

             else

               {

                 f[i*p[j]]=f[i]/(sum[i]+)*(sum[i]+);

                 sum[i*p[j]]=sum[i]+;

               }

           }

         ans+=f[i];

       }

     printf("%lld\n",ans);

     return ;

 }