轉載至https://blog.csdn.net/skywalkert/article/details/50500009

前置技能

積性函數的定義

若f(n)f(n)的定義域為正整數域，值域為復數，即f:Z+→Cf:Z+→C，則稱f(n)f(n)為數論函數。

若f(n)f(n)為數論函數，且f(1)=1f(1)=1，對于互質的正整數p,qp,q有f(p?q)=f(p)?f(q)f(p?q)=f(p)?f(q)，則稱其為積性函數。

若f(n)f(n)為積性函數，且對于任意正整數p,qp,q都有f(p?q)=f(p)?f(q)f(p?q)=f(p)?f(q)，則稱其為完全積性函數。

積性函數的性質與例子

狄利克雷卷積與莫比烏斯反演

ACM賽題是需要這種技巧在低于線性時間的復雜度下解決一類積性函數的前綴和問題。

首先看一個簡單的例子，求前nn個正整數的約數之和，即，其中。?
顯然不能直接做了，但是我們可以推導一番：

如果能通過狄利克雷卷積構造一個更好計算前綴和的函數，且用于卷積的另一個函數也易計算，則可以簡化計算過程。例如上題就是利用了的性質，但一定注意，不是所有的這一類題都只用配個恒等函數II就可以輕松完事的，有時需要更細致的觀察。

?

?

但是注意到這種方法的常數與復雜度都可能較高，有時候可能再進行一些推導可以得到一個不使用正文方法的做法，例如ZOJ 3881 - From the ABC conjecture，本文的方法與網上一個解法類似，可以用于求解此題，但是可以這樣推導之后得到更簡單的一個做法。

需要使用此種方法的題目一般數據規模較大，例如，但是并不是都要使用此類方法，有時候可能存在其他O()的做法，例如51Nod 1222 - 最小公倍數計數，會利用正文復雜度分析的方法即可，再例如ZOJ 5340 - The Sum of Unitary Totient

推薦題目

這里給出一些練手的題目供大家理解上述方法，這類題還是較少的，如有其他題的題源歡迎分享。?
51Nod 1244 - 莫比烏斯函數之和?
51Nod 1239 - 歐拉函數之和?
BZOJ 3944 - Sum?
HDU 5608 - function?
51Nod 1238 - 最小公倍數之和 V3?
51Nod 1237 - 最大公約數之和 V3?
51Nod 1227 - 平均最小公倍數?
Tsinsen A1231 - Crash的數字表格?
SPOJ DIVCNT2 - Counting Divisors (square)?
51Nod 1222 - 最小公倍數計數（復雜度分析）?
BZOJ 4176 - Lucas的數論?
51Nod 1220 - 約數之和?
51Nod 1584 - 加權約數和?
ZOJ 3881 - From the ABC conjecture（不需要使用正文方法）?
BZOJ 3512 - DZY Loves Math IV?
ZOJ 5340 - The Sum of Unitary Totient（常規積性函數求和，數據組數較多，只可分段打表）?
SPOJ DIVCNT3 - Counting Divisors (cube)（常規積性函數求和，注意代碼長度限制，不可打表）?
51Nod 1575 - Gcd and Lcm（常規積性函數求和，可分段打表）?
51Nod 1847 - 奇怪的數學題（非常規積性函數求和，綜合題，可分段打表）

?

?

總結

以上是生活随笔為你收集整理的浅谈积性函数求前缀和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。