莫比乌斯反演 HDU1695 GCD

莫比乌斯函数

【通俗理解】

我们手里有两个函数，不妨F(x)和f(x)，且F(x)是易知的，满足上述(1)(2)中任意一个，则我们可以通过莫比乌斯反演得出f(n)的函数值。

【莫比乌斯函数求法】

如果我们会素数的线性筛求法，那就在线性筛过程中可以一并求出莫比乌斯函数。

代码：https://paste.ubuntu.com/p/5JX7KHW8Rc/

【例题 HDU 1695 GCD】

题意：

给出5个整数a,b,c,d,k，题目保证a=c=1; 对于x；x∈[a,b],y∈[c,d],求gcd(x,y)=k的个数。本题中x y互换视为同一个！

分析：

不妨设F(x)=( gcd(x,y)=k的倍数的数量 )，设f(x)=( gcd(x,y)=k的数量 )，显然存在倍数关系，满足(2)。

通过反演即可得出 f ( k ) = ∑ d ∣ k μ ( d k ) F ( d ) f(k)=\sum_{d|k} μ(\frac{d}{k}) F(d) f(k)=d∣k∑​μ(kd​)F(d)

由gcd(x,y)=1可得gcd(xk,yk)=k，因此上述a,b,c,d均除以k之后，就相当于求f(1)了。 F(x)是已知的： F ( x ) = ( b x ) ∗ ( d x ) F(x) = (\frac{b}{x})*(\frac{d}{x}) F(x)=(xb​)∗(xd​)

所以f(1)可以在线性时间内求出来。

【代码】：https://paste.ubuntu.com/p/MGJvFJXxgm/

优化解法：

枚举F(i)的i时，发现一段连续的i，其实F(i)是相等的，所以这一个块可以一次性计算出来。有这个优化后，HDUOJ耗时0MS.

【代码-优化】：https://paste.ubuntu.com/p/22bNdnwqN8/

还有一种解法，打一张矩形表，根据规律筛选，看代码好理解，不过时间复杂度O(n*logn)，比莫比乌斯反演的线性复杂度慢一些。

【代码-普通】：https://paste.ubuntu.com/p/8nvcRh9Qz6/