[bzoj3944] sum [杜教筛模板]

题面：

就是让你求$ \varphi\left(i\right) $以及$ \mu\left(i\right) $的前缀和

思路：

就是杜教筛的模板

我们把套路公式拿出来：

$ g\left(1\right)S\left(n\right)=\sum_{i=1}^{n}\left(g\ast f\right)\left(i\right)-\sum_{i=2}^{n}g\left(i\right)S\left(\frac ni\right) $

其中函数$f$分别为$\varphi$以及$\mu$

对于这两个函数有两个非常好用的卷积公式：

$\left(\mu\ast I\right)=\varepsilon$

$\left(\varphi\ast I\right)=id$

那么我们设g(x)=1，然后把g(x)带进去，两个前缀和就变成了这样的：

$S\left(n\right)=1-\sum_{i=2}^{n}S\left(\frac ni\right)$这个是$\mu$

$S\left(n\right)=\frac{n\ast\left(n+1\right)}{2}-\sum_{i=2}^{n}S\left(\frac ni\right)$这个是$\varphi$

然后递归，记忆化求和就可以了

注意最好写成一个递归处理两个答案......不然会T成狗

Code：

这里提供两个函数分开的版本，方便查看

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<map>

 #define ll long long

 using namespace std;

 inline ll read(){

     ll re=,flag=;char ch=getchar();

     while(ch>''||ch<''){

         if(ch=='-') flag=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();

     return re*flag;

 }

 ll phi[],pri[],tot=,mu[],n;bool vis[];

 void init(){

     ll i,j,k;phi[]=mu[]=;phi[]=;

     for(i=;i<=;i++){

         if(!vis[i]){

             pri[++tot]=i;phi[i]=i-;mu[i]=-;

         }

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

             k=i*pri[j];if(k>) break;

             vis[k]=;

             if(i%pri[j]==){

                 phi[k]=phi[i]*pri[j];

                 mu[k]=;

                 break;

             }

             phi[k]=phi[i]*phi[pri[j]];

             mu[k]=-mu[i];

         }

     }

     for(i=;i<=;i++) phi[i]=phi[i-]+phi[i],mu[i]=mu[i-]+mu[i];

 }

 ll sum1(ll x){return x*(x+)/;}

 ll v1[],v2[],m1[],m2[];

 ll S1(ll x){

     if(x<=) return phi[x];

     ll re=sum1(x);ll i,j,t=n/x;

     if(v1[t]) return m1[t];

     for(i=;i<=x;i=j+){

         j=x/(x/i);

         re-=(j-i+)*S1(x/i);

     }

     v1[t]=;

     return m1[t]=re;

 }

 ll S2(ll x){

     if(x<=) return mu[x];

     ll re=,i,j,t=n/x;

     if(v2[t]) return m2[t];

     for(i=;i<=x;i=j+){

         j=x/(x/i);

         re-=(j-i+)*S2(x/i);

     }

     v2[t]=;

     return m2[t]=re;

 }

 int main(){

     ll T=read();init();

     while(T--){

         n=read();memset(v1,,sizeof(v1));memset(v2,,sizeof(v2));

         printf("%lld %lld\n",S1(n),S2(n));

     }

 }

巴特西

[bzoj3944] sum [杜教筛模板]

最新文章

热门文章