【算法笔记】杜教筛

$$\left\{ {\begin{array}{*{20}{l}} {f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\ {(\varphi \times I)(x) = id}\\ {g(n) = \sum\limits_{i = 1}^n {id(i)} } \end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})}$$

【BZOJ 3944】Sum

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000+9;
const int MX = 5000000;

int mu[N],cnt,pri[N];
bool vis[N]; LL phi[N];
map<int,int> MU;
map<int,LL> PHI;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void prework(){
mu[1] = phi[1] = 1;
for (int i=2;i<=MX;i++) {
if (!vis[i]) pri[++cnt] = i, mu[i] = -1, phi[i] = i-1;
for (int j=1,w;j<=cnt && pri[j]*i<=MX;j++) {
vis[i*pri[j]] = 1; w = pri[j]*i;
if (i%pri[j]) mu[w] = -mu[i], phi[w] = phi[i]*(pri[j]-1);
else {phi[w] = phi[i]*pri[j]; break;}
}
}
for (int i=1;i<=MX;i++) mu[i] += mu[i-1], phi[i] += phi[i-1];
}

inline int solve_mu(int w) {
if (w <= MX) return mu[w];
else if (MU[w]) return MU[w];
else {
int ret = 1;
for (LL i=2,tmp;i<=w;i=tmp+1) {
tmp = w / (w / i);
ret -= solve_mu(w/tmp)*(tmp-i+1);
} MU[w] = ret; return ret;
}
}

int LL solve_phi(int w) {
if (w <= MX) return phi[w];
else if (PHI[w]) return PHI[w];
else {
LL ret = w * ((LL)w+1) / 2;
for (LL i=2,tmp;i<=w;i=tmp+1) {
tmp = w / (w/i);
ret -= solve_phi(w/tmp)*(tmp-i+1);
} PHI[w] = ret; return ret;
}
}

int main(){
prework();
printf("%lld %d\n",solve_phi(w),solve_mu(w));
return 0;
}


【51NOD 1244】莫比乌斯函数之和

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000+9;
const int MX = 5000000;

int mu[N],cnt,pri[N];
bool vis[N];
unordered_map<LL,LL> M;

inline int prework(){
mu[1] = 1;
for (int i=2;i<=MX;i++) {
if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
for (int j=1;j<=cnt && pri[j]*i<=MX;j++) {
vis[i*pri[j]] = 1;
if (i%pri[j]) mu[i*pri[j]] = -mu[i];
else break;
}
}
for (int i=1;i<=MX;i++) mu[i] += mu[i-1];
}

inline LL solve(LL w) {
if (w <= MX) return mu[w];
else if (M[w]) return M[w];
else {
LL ret = 1;
for (LL i=2,tmp;i<=w;i=tmp+1) {
tmp = w / (w / i);
ret -= solve(w/tmp)*(tmp-i+1);
} M[w] = ret; return ret;
}
}

int main(){
prework(); LL a,b; cin>>a>>b;
printf("%d\n",solve(b)-solve(a-1));
return 0;
}


【51NOD 1239】欧拉函数之和

$$\left\{ {\begin{array}{*{20}{l}} {f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\ {(\varphi \times I)(x) = id}\\ {g(n) = \sum\limits_{i = 1}^n {id(i)} } \end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})}$$

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int REV = 500000004;
const int MX = 5000000;
const int N = MX + 9;

unordered_map<LL,int> M;
int phi[N],pri[N],tot;
bool vis[N];

char c=getchar(); LL ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret;
}

inline void prework(){
phi[1] = 1;
for (int i=2;i<=MX;i++) {
if (!vis[i]) pri[++tot] = i, phi[i] = i - 1;
for (int j=1;j<=tot && pri[j]*i<=MX;j++) {
vis[pri[j]*i] = 1;
if (i%pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1);
else {phi[i*pri[j]] = phi[i]*pri[j]; break;}
}
}for (int i=1;i<=MX;i++) phi[i] += phi[i-1], phi[i] %= MOD;
}

int solve(LL w) {
if (w <= MX) return phi[w];
else if (M[w]) return M[w];
else {
int ret = ((w%MOD)*((w+1)%MOD)%MOD)*REV%MOD;
for (LL i=2,tmp;i<=w;i=tmp+1) {
tmp = w / (w/i); ret %= MOD;
ret -= (LL)solve(w/tmp)*(tmp-i+1) % MOD;
} ((ret%=MOD)+=MOD)%=MOD; M[w] = ret; return ret;
}
}

int main(){
prework();