在數(shù)論中，有很多題目都與莫比烏斯反演有關(guān)，最典型的就是最大公約數(shù)。比如你可以見到如下常見問題。

?

（1）已知，求為質(zhì)數(shù)的的對(duì)數(shù)，或者等于1的的對(duì)數(shù)。

?

（2）已知和，求為質(zhì)數(shù)的的對(duì)數(shù)，或者等于1的的對(duì)數(shù)。

?

（3）已知，求的對(duì)數(shù)。

?

（4）已知和，求的對(duì)數(shù)。

?

上面的問題其實(shí)都可以用莫比烏斯反演來解，時(shí)間復(fù)雜度都還可以。關(guān)于莫比烏斯反演，前面的文章中有詳細(xì)介紹。

?

莫比烏斯反演：http://blog.csdn.net/acdreamers/article/details/8542292

?

?

接下來，我們看一個(gè)關(guān)于莫比烏斯反演稍微復(fù)雜一點(diǎn)的題目。

?

題目：http://acm.fzu.edu.cn/problem.php?pid=2106

?

題意：給一個(gè)長度小于20的整數(shù)數(shù)組a[]，有另外一個(gè)數(shù)組b[]，滿足條件，求使得條件

???? 成立的數(shù)組b[]的個(gè)數(shù)，結(jié)果對(duì)取余。

?

分析：依據(jù)前面學(xué)的莫比烏斯反演，我們先設(shè)兩個(gè)函數(shù)和。

?

???? 為滿足條件的對(duì)數(shù)

?

???? 為滿足條件的對(duì)數(shù)

?

?????那么，很明顯有 ，注意這里的為公共因子。

?

???? 而，反演后得到

?

???? 在這里我們只考慮為無平方因子的數(shù)即可。

?

?

?

總結(jié)

以上是生活随笔為你收集整理的莫比乌斯反演与最大公约数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。