锐客网

  1. 首页 > it技术 > >

杜教筛 51Nod_P1244 莫比乌斯函数求和

杜教筛

题目大意：
求：
杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

2<=a<=b<=10^10
题目分析：
首先这道题很显然可以拆成两个前缀和相减的形式，即如何求：∑（1<=i<=n）μ(i)
当n很小的时候，我们只要线性筛一下莫比乌斯函数就可以了。
但是这道题数据范围很大，所以就要考虑杜教筛。
杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

【杜教筛 51Nod_P1244 莫比乌斯函数求和】我们所求即为f（n）
杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

中间那步不懂的小伙伴看这里：
对于第一个等号后面那个式子，相当于先枚举i，再枚举i的约数，然后求和。
于是这一步就相当于：
杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

此处的x*d就相当于上一个式子中的 i，x相当于d|i时的i/d，即i的另一个约数。
我们枚举这个x，当x固定时，为了满足x*d<=n，d只能枚举到n/x。
即：杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

我们用i来替换里面的x就得到了第二个等号后的式子。
这里就是这么转化过来的。
所以我们所求就转化成了：
杜教筛 51Nod_P1244 莫比乌斯函数求和
文章图片

这样我们先筛除一部分f（n），然后根据n/i的值对i进行分块，递归处理f（n/i）。
这个也可以记忆化一下，可以自己写hash，C++选手可以用map。
时间复杂度O（n^(2/3)) （如果用map的话还要乘个log，话说这个2/3次方时怎么出来的真心不知道啊QAQ)
代码如下：

#include #include #include #define N 20000000 using namespace std; long long a,b,n; int mu[N+10],pri[1300010],top; bool mark[N+10]; mapV; void shake() { mu[1]=1; for(int i=2; i<=N; i++) { if(!mark[i]) { pri[++top]=i; mu[i]=-1; } for(int j=1; j<=top && i*pri[j]<=N; j++) { mark[i*pri[j]]=true; if(i%pri[j]==0) break; mu[i*pri[j]]=-mu[i]; } } for(int i=2; i<=N; i++) mu[i]+=mu[i-1]; } long long calc(long long x) { if(x<=N) return mu[x]; if(V[x]) return V[x]; long long ans=1; for(long long i=2,r; i<=x; i=r+1) { r=x/(x/i); ans-=calc(x/i)*(r-i+1); } V[x]=ans; return ans; } int main() { shake(); cin>>a>>b; cout<

    推荐阅读


    上一篇：ELF section修复的一些思考

    下一篇：Linux下脚本对拍