杜教筛 [理解+模板]

​​传送门​​

杜教筛解决这类问题: 

求            其中  

 

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

 于是要求的变成

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

---

本题的解决方案

 

当 f 为 mu 时, 考虑

令g = I, 那么

 

当 f 为 phi 时, 考虑

令 g = I

---

时间复杂度的分析

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

---

#include<bits/stdc++.h>
#define N 5000050
#define LL long long
using namespace std;
int T;
int prim[N],isp[N],tot;
int mu[N]; LL phi[N];
map<int,int> Mu;
map<int,LL> 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;
}