ACM-ICPC 2018 南京赛区网络预赛Sum，线性筛处理积性函数

　　题意：f(n)是n可以拆成多少组n=a*b，a和b都是不包含平方因子的方案数目，对于a!=b,n=a*b和n=b*a算两种方案，求∑_i=1ⁿf(i)

　　首先我们可以知道，n=1时f(1)=1，

　　然后我们继续分析，当n为素数p时，只能拆成n=1*p和n=p*1这两种，所以f(p)=2，

　　而当n=两个质数的乘积时,对于n=左*右，p₁跟p₂可以任意分配在左和右，它们的方案是类乘的，所以f(p₁*p₂)=f(p₁)*f(p₂)

　　这里可以看出f(n)是个积性函数，那说明我们可以把它通过线性筛筛出来。

　　那我们就要考虑n=p^k的时候，当k>2时，对于n=左*右，不管哪个方案，左或者右那边必定有一边是存在因子包含p²的，所以此时f(p^k)=0,k>2

　　k=1时便是n=p，而k==2时呢，p只能分别在左右两边各一个，f(p²)=1

　　最后推广n=p₁^k1*p₂^k2的时候，k1,k2肯定都不能>2，然后就是(0,0),(0,1),(0,2),(1,0),(1,1,)(1,2),(2,0)(2,1)(2,2)这九种，推导一下就是f(p₁^k1*p₂^k2)=f(p₁^k1)*f（p₂^k2)

　　具体编程实现上的话，因为欧拉筛对于每个数来说，是通过它的最小质因子来筛掉它，那么我们可以记录每个数的最小质因子的指数exp，详情见注释

 #include<cstdio>

 typedef long long ll;

 const int N=;

 bool nop[N]={false};

 int pn,pri[N/],exp[N],f[N];

 void init()

 {

     f[]=;

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

     {

         if(!nop[i])

         {

             f[i]=;

             exp[i]=;

             pri[pn++]=i;

         }

         for(int j=;j<pn&&1ll*i*pri[j]<N;j++)

         {

             int pp=i*pri[j];

             nop[pp]=true;

             //欧拉筛中，pri[j]是pp的最小质因子

             if(i%pri[j]==)

             {

                 //i的质因子有pri[j],pp的最小质因子的指数就是exp[i]+1

                 exp[pp]=exp[i]+;

                 if(exp[pp]>)

                     f[pp]=;

                 else

                     f[pp]=f[i/pri[j]];

                 //在i的方案上，再加入一个pri[j]，不能跟i中原来有的

                 //pri[j]在同一边，而在对立边时,i中原来有的pri[j]

                 //在左，在右都一样，对方案没有了影响，所以

                 //f[i*pri[j]]=f[i/pri[j]];

                 break;

             }

             //i的质因子没有pri[j]，那么pp中只有一个pri[j]

             exp[pp]=;

             f[pp]=f[i]*f[pri[j]];

         }

     }

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

         f[i]+=f[i-];

 }

 int main()

 {

     init();

     int t,n;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         printf("%d\n",f[n]);

     }

     return ;

 }

线性啊欧拉啊

　　对于f[pp]=f[i/pri[j]]处，我说得不是很清楚，也不知道怎么表达那个意思，可以自行模拟体会一下。

巴特西

ACM-ICPC 2018 南京赛区网络预赛Sum，线性筛处理积性函数

最新文章

热门文章