莫比烏斯反演 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/