杜教筛 [理解+模板]

杜教筛 [理解+模板]

​​传送门​​

杜教筛解决这类问题:

我们寻找一个函数 g, 看能不能求出

看看我们要什么 (g为积性函数 -> g(1) = 1)

于是要求的变成

我们选出g 使第一个很好求, 然后第二个可以整除分块递归下去

本题的解决方案

当 f 为 mu 时, 考虑

令g = I, 那么

当 f 为 phi 时, 考虑

令 g = I

时间复杂度的分析

然后可以线性筛预处理<=m 的值, 反正空间开得下就尽量多处理一些就可以了

#include#define N 5000050#define LL long longusing namespace std;int T;int prim[N],isp[N],tot;int mu[N]; LL phi[N];map Mu;map Phi; void prework(){ mu[1] = phi[1] = 1; for(int i=2;i<=N-50;i++){ if(!isp[i]) prim[++tot] = i, mu[i] = -1, phi[i] = i-1; for(int j=1;j<=tot;j++){ if(i * prim[j] > N -50) break; isp[i * prim[j]] = 1; if(i % prim[j] == 0){ mu[i * prim[j]] = 0; phi[i * prim[j]] = phi[i] * (LL)prim[j]; break; } else{ mu[i * prim[j]] = -mu[i]; phi[i * prim[j]] = phi[i] * (LL)(prim[j] - 1); } } } for(int i=2;i<=N-50;i++) mu[i] += mu[i-1], phi[i] += phi[i-1];}LL get_Phi(int x){ if(x<=N-50) return phi[x]; if(Phi[x]) return Phi[x]; LL ans = (LL)x * (LL)(x+1) / 2; for(int l=2,r;l<=x;l=r+1){ int val = x/l; r = x/val; ans -= (LL)(r-l+1) * get_Phi(val); } return Phi[x] = ans;}int get_Mu(int x){ if(x<=N-50) return mu[x]; if(Mu[x]) return Mu[x]; int ans = 1; for(int l=2,r;l<=x;l=r+1){ int val = x/l; r = x/val; ans -= (r-l+1) * get_Mu(val); } return Mu[x] = ans;}int main(){ prework(); scanf("%d",&T); while(T--){ int n; scanf("%d",&n); printf("%lld %d\n", get_Phi(n), get_Mu(n)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。