首页 > 代码库 > 【51nod-1239&1244】欧拉函数之和&莫比乌斯函数之和 杜教筛
【51nod-1239&1244】欧拉函数之和&莫比乌斯函数之和 杜教筛
题目链接：
1239：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1239
1244：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1244
杜教筛裸题，不过现在我也只会筛这俩前缀和...
$$s(n)=\sum _{i=1}^{n}f(i)$$
那么就有：
$$\sum_{i=1}^{n}f(i)\lfloor \frac{n}{i} \rfloor=\sum_{i=1}^{n}s(\lfloor \frac{n}{i} \rfloor)=s(n)+\sum_{i=2}^{n}s(\lfloor \frac{n}{i} \rfloor)$$
移项得到：
$$s(n)=\sum_{i=1}^{n}f(i)\lfloor \frac{n}{i} \rfloor-\sum_{i=2}^{n}s(\lfloor \frac{n}{i} \rfloor)$$
对于欧拉函数，$f(n)=\phi(n)$
$$\sum_{i=1}^{n}\phi(i)\lfloor \frac{n}{i} \rfloor=\sum_{i=1}^{n}\sum_{d|n}\phi(d)=\sum_{i=1}^{n}i=\frac{n*(n+1)}{2}$$
对于莫比乌斯函数，$f(n)=\mu(n)$
$$\sum_{i=1}^{n}\mu(i)\lfloor \frac{n}{i} \rfloor=\sum_{i=1}^{n}\sum_{d|n}\mu(d)=\sum_{i=1}^{n}[i=1]=1$$
然后这两个公式就可以在线筛预处理$n^{\frac{2}{3}}$只后记忆化达到$O(n^{\frac{2}{3}})$的效率.
值得注意的就是，记忆化要写hash，以及不要忘了取模，筛欧拉函数前缀和时牵扯取模和除2，可以先讨论奇偶除掉2再计算。
1239：
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>using namespace std;#define LL long long#define N 5000000#define P 233333#define MAXN 250000#define MO 1000000007int cnt,prime[N+10],flag[N+10];LL X,phi[N+10];inline void Pre(LL n){ flag[1]=1; phi[1]=1; for (LL i=2; i<=n; i++) { if (!flag[i]) prime[++cnt]=i,phi[i]=i-1; for (int j=1; j<=cnt && i*prime[j]<=n; j++) { flag[i*prime[j]]=1; if (!(i%prime[j])) {phi[i*prime[j]]=phi[i]*prime[j]; break;} phi[i*prime[j]]=phi[i]*(prime[j]-1); } } for (LL i=1; i<=n; i++) phi[i]=(phi[i]+phi[i-1])%MO;}struct Hash{ int next; LL i,x;}mp[MAXN];int head[MAXN],tot;inline void Add(LL i,LL x) {int pos=i%P; tot++; mp[tot].next=head[pos]; head[pos]=tot; mp[tot].i=i; mp[tot].x=x;}inline LL Sum(LL x){ if (x<=N) return phi[x]; else { int pos=x%P; for (int i=head[pos]; i; i=mp[i].next) if (mp[i].i==x) {return mp[i].x;} } LL sum=0,s=0; for (LL i=2,j; i<=x; i=j+1) j=x/(x/i),(sum+=Sum(x/i)%MO*(j-i+1)%MO)%=MO; if (x&1) s=(((x+1)/2)%MO)*(x%MO)%MO; else s=((x/2)%MO)*((x+1)%MO)%MO; sum=(s-sum+MO)%MO; Add(x,sum); return sum; }int main(){ scanf("%lld",&X); Pre(N); printf("%lld\n",Sum(X)); return 0;}1244
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;#define LL long long#define P 233333#define N 5000000#define MAXN 250000int cnt,prime[N+10],flag[N+10];LL L,R,mu[N+10];inline void Pre(LL n){ flag[1]=1; mu[1]=1; for (LL i=2; i<=n; i++) { if (!flag[i]) prime[++cnt]=i,mu[i]=-1; for (int j=1; j<=cnt && i*prime[j]<=n; j++) { flag[i*prime[j]]=1; if (!(i%prime[j])) {mu[i*prime[j]]=0; break;} mu[i*prime[j]]=-mu[i]; } } for (LL i=1; i<=n; i++) mu[i]+=mu[i-1];}struct Hash{ int next; LL i,x;}mp[MAXN];int head[MAXN],tot;inline void Add(LL i,LL x) {int pos=i%P; tot++; mp[tot].next=head[pos]; head[pos]=tot; mp[tot].i=i; mp[tot].x=x;}inline LL Sum(LL x){ if (x<=N) return mu[x]; else { int pos=x%P; for (int i=head[pos]; i; i=mp[i].next) if (mp[i].i==x) {return mp[i].x;} } LL sum=0; for (LL i=2,j; i<=x; i=j+1) j=x/(x/i),sum+=Sum(x/i)*(j-i+1); Add(x,1LL-sum); return 1LL-sum;}int main(){ scanf("%lld%lld",&L,&R); Pre(N); printf("%lld\n",Sum(R)-Sum(L-1)); return 0;}
【51nod-1239&1244】欧拉函数之和&莫比乌斯函数之和 杜教筛