容斥原理|[BZOJ 2301] Problem b【莫比乌斯反演/容斥原理/分块】莫比乌斯反演|BZOJ|分块

[Description] 有n个询问(n≤50000),每个询问有五个整数a,b,c,d,k,求有多少个数对(x,y)满足a≤x≤b，c≤y≤d，且gcd(x,y)=k.(a≤b≤50000,c≤d≤50000,k≤50000)
[Solution]
我们发现，计算一个数x在某个闭区间[a,b]内的因数数量并不是很方便，可以转化为x在区间[1,b]的因数的数量-x在区间[1,a-1]的因数的数量（因为求[1,Z]比较好求）。
原问题是，对于所有x∈[a,b],y∈[c,d]，求所有gcd(x,y)=k的点对的数量。
根据容斥原理，问题转化为，计算:
所有x∈[1,b],y∈[1,d],所有gcd(x,y)=k的点对的数量
-所有x∈[1,a-1],y∈[1,d],所有gcd(x,y)=k的点对的数量
-所有x∈[1,b],y∈[1,c-1],所有gcd(x,y)=k的点对的数量
+所有x∈[1,a-1],y∈[1,c-1],所有gcd(x,y)=k的点对的数量
所以怎么求解任意x∈[1,n],y∈[1,m],所有gcd(x,y)=k的点对的数量呢？
设f(k)=任意x∈[1,n],y∈[1,m],所有gcd(x,y)=k的点对的数量,我们发现并不好求，于是再设F(k)=任意x∈[1,n],y∈[1,m],所有满足k整除gcd(x,y)的点对的数量
因为F值比f值容易求，所以我们这时可以运用莫比乌斯反演了。
容易发现，只要是k的倍数的f值都对F(k)有贡献，即
文章图片
即可以推出
文章图片

我们可以知道F(k)=floor(n/k)*floor(m/k)，即n内有n/k个数是k的倍数，m内有n/k个数是k的倍数，他们两两之间的最小公因数一定包含k。
于是
文章图片

这样我们就可以在线性时间求出f的值了。
然而我们发现，每个询问的需要计算四个f，复杂度依然达到平方级，仍需优化。
还有哪里可以优化呢？
我们发现，其实有一些k,他们的floor(n/k)*floor(m/k)是一样的，我们还要对他们分别求和，拉慢了运行速度。
因为不同floor(n/k)floor(m/k)值最多2 (sqrt(n)+sqrt(m))个（证明如下）
可以发现，floor(n/k)的值最多2*sqrt(n)个(小于sqrt(n)的因数x对应一个大于sqrt(n)的因数n/x)，我们将floor（n/k）值相等的k在数轴上分到一个区间，（如下图），则最多2*sqrt(n)个区间，相同的，floor（m/k）值相等的k最多2*sqrt(m)个区间,以n=6,m=8为例。

文章图片

就是说，floor(n/k)有2*sqrt(n/k)取值，floor(n/k)有3*sqrt(n/k)取值，它们对应起来的取值，就是划分的2*(sqrt(n/k)+sqrt(m/k))区间的区间。

文章图片

且floor(n/k)*floor(m/k)值相同的k显然是连续的，我们可以对μ求一下前缀和，对于值相同的k直接乘上他们的μ值和即可，这样就可以将复杂度优化到O(n *sqrt(max(b,d)))了。
然而我们怎么找到每个区间的起点和终点呢?我们发现，m/k可以找到floor值为k的区间的末尾值，例如第一个数轴中6/floor(6/5)可以找到5所在区间的末尾6，第二个数轴中8/floor(8/5)可以找到5所在区间的末尾8，这样，区间起点为i，这个区间末尾就是min(floor(n/(n/i)),floor(m/(m/i))).
其实还可以更优化，求所有x∈[a,b],y∈[c,d]，求所有gcd(x,y)=k的点对的数量可转化为x∈[a/k,b/k],y∈[c/k,d/k]，求所有gcd(x,y)=1的点对的数量，只要在程序里加一句话就可以提速50%了，留给读者自己思考。
之后的事就非常愉快辣！
【容斥原理|[BZOJ 2301] Problem b【莫比乌斯反演/容斥原理/分块】】[Code]

#include #include using namespace std; const int maxn=50000+10; bool form[maxn]; int prime[maxn],mu[maxn]={0,1},sum[maxn],cnt; void MakeMuList(){ for(int i=2; im) swap(n,m); for(int i=1,last; i<=n; i=last+1){ last=min(n/(n/i),m/(m/i)); ans+=(sum[last]-sum[i-1])*(m/(i*k))*(n/(i*k)); } return ans; }int main(){ MakeMuList(); int kase; scanf("%d",&kase); while(kase--){ int a,b,c,d,k; scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); printf("%d\n",f(b,d,k)-f(a-1,d,k)-f(b,c-1,k)+f(a-1,c-1,k)); } return 0; }

容斥原理|[BZOJ 2301] Problem b【莫比乌斯反演/容斥原理/分块】

推荐阅读

redmi|再爆新品！Redmi Watch 2将于28日发布这次有点猛！

长沙跨境电商公司长沙电商平台众联什么样，长沙比较大的电商公司有哪些

香榧吃了会不会胖香榧相关介绍

如何解决人脸识别服务器超时问题？人脸识别服务器超时怎么办

贫血吃什么

违章代码1355是什么意思

财务报表分析程序

学什么舞蹈能提升气质

云朵简笔画云朵简笔画怎么画

别客气用英语怎么说 welcome

分布式理论

golang获取命令行参数方法总结

玻尿酸丰胸多少钱_玻尿酸丰胸和假体丰胸哪种好

四年级我就这样长大了作文3篇

QQ飞车手游荣耀勋章第9期车大全：荣耀勋章第九期全部奖励总汇

唐朝皇帝后宫女人等级是如何，唐朝宫女等级制度

刚做完流产已经三天没吃饭只喝点水解

喊山红霞被判几年

gis罐体外卡式，gis罐体常用材料

大巴车载客人数中型客车核载多少人