P4213【模板】杜教筛（Sum）

思路：杜教筛

提交：$2$次

错因：$\varphi(i)$的前缀和用$int$存的

题解：

对于一类筛积性函数前缀和的问题，杜教筛可以以低于线性的时间复杂度来解决问题。

先要构造$h=f*g$，并且$h$的前缀和易求，$g$的区间和易求。

具体地：

\[\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}g(d)\cdot f(\frac{i}{d})$$ $$\sum_{i=1}^{n}h(i)=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f({i})
\]

设$S(n)$表示$\sum_{i=1}^{n}f(i)$

\[\sum_{i=1}^{n}h(i)=\sum_{d=1}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
\]

\[g(1)\cdot S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
\]

当我们对后面的式子进行整除分块时，求$S(n)$的复杂度为$O(n^{\frac{2}{3}})$

所以主要就是如何构造$h$和$g$

好吧直接说了：

$\epsilon=\mu\cdot I$

$id=\varphi\cdot I$

对于$f(n)=\varphi(n)\cdot n^k=\varphi(n^{k+1})$的一类方法：

$id^{k+1}=f\cdot id^k$

#include<cstdio>

#include<iostream>

#include<unordered_map>

#include<cmath>

#define ll long long

#define R register int

using namespace std;

namespace Luitaryi {

template<class I> inline I g(I& x) { x=0; register I f=1;

  register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;

} const int N=5000000,Inf=2147483647;

int T,n,cnt,p[N/4],mu[N+10];

ll phi[N+10];

bool v[N+10];

inline void PRE() { phi[1]=mu[1]=1;

  for(R i=2;i<=N;++i) {

    if(!v[i]) p[++cnt]=i,phi[i]=i-1,mu[i]=-1;

    for(R j=1;j<=cnt&&i*p[j]<=N;++j) {

      v[i*p[j]]=true;

      if(i%p[j]==0) {

        mu[i*p[j]]=0;

        phi[i*p[j]]=phi[i]*p[j]; break;

      } mu[i*p[j]]=-mu[i];

      phi[i*p[j]]=phi[i]*(p[j]-1);

    }

  }

  for(R i=1;i<=N;++i) mu[i]+=mu[i-1];

  for(R i=1;i<=N;++i) phi[i]+=phi[i-1];

}

unordered_map<int,int> memmu;

unordered_map<int,ll> memphi;

inline ll s_phi(int n) {

  if(n<=N) return phi[n];

  if(memphi.count(n)) return memphi[n];

  register ll ans=0;

  for(R l=2,r;r<Inf&&l<=n;l=r+1) {

    r=n/(n/l),ans+=(r-l+1)*s_phi(n/l);

  } return memphi[n]=1llu*n*(n+1ll)/2ll-ans;

}

inline int s_mu(int n) {

  if(n<=N) return mu[n];

  if(memmu.count(n)) return memmu[n];

  register ll ans=0;

  for(R l=2,r;r<Inf&&l<=n;l=r+1) {

    r=n/(n/l),ans+=(r-l+1)*s_mu(n/l);

  } return memmu[n]=1ll-ans;

}

inline void main() {

  PRE(); g(T); while(T--) {

    g(n); printf("%lld %d\n",s_phi(n),s_mu(n));

  }

}

} signed main() {Luitaryi::main(); return 0;}

2019.08.23

77

巴特西

P4213【模板】杜教筛（Sum）

思路：杜教筛

提交：\(2\)次

错因：\(\varphi(i)\)的前缀和用\(int\)存的

题解：

最新文章

热门文章