【參考】

★淺談一類積性函數的前綴和 by?skywalkert

任之洲數論函數.pdf

論逗逼的自我修養之寒假頹廢記?by?jiry_2

杜教篩 [學習筆記]【更新中】?by?Candy?

?

【變化技巧總結】

總結下面所有知識含有的變化技巧

1.先枚舉gcd值。

2.莫比烏斯反演處理gcd，[gcd(x,y)=1]=Σ_d|i^d|jμ(d)，然后將d提到最前面。

3.★分塊取值優化，ans=Σf(d)*g(n/d)，其中g(n/d)只有2√n種取值，預處理f(d)的前綴和即可O(√n)。

4.多組詢問時，對于ΣdΣe，令T=de，則ΣTΣd|T，后面枚舉倍數貢獻可以O(n ln n)預處理前綴和。

5.杜教篩：倍數和總數互換，即

$sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}ze8trgl8bvbq)=\sum_{i=1}^{n}\sum_{d=1}^{\frac{n}{i}}f(d)g(i)=\sum_{i=1}^{n}g(i)F(\frac{n}{i})$

用這個變化，對于卷積f*g=h，知二求一。

6.函數為加法時，可以分別統計前綴和再相加，但乘法必須一起統計。

?

例題：【51nod】1238 最小公倍數之和 V3 杜教篩

1.相同的完全積性函數卷積有奇效（在這題是同階冪函數卷積）。

2.矩陣轉上三角，就可以變成積性函數前綴和的形式。

3.狄利克雷卷積有交換律，結合律，加法分配律。點乘有卷積分配律，即a(b*c)=ab*ac。

4.φ也可以化簡[(n,i)=1]，不一定用μ。

?

例題：【Project Euler】530 GCD of Divisors 莫比烏斯反演

1.對于[(a,b)=d]，可以將共有因子d提出來并壓縮枚舉空間。

2.約數個數前綴和可以O(√n)，看到可以轉化過去。

3.兩個Σ1~n，可以合并為枚舉乘積，然后變成卷積的形式。

4.復雜度不一定是看到的那樣，要好好分析或好好感受。

?

【積性函數】

積性函數的約數和，前綴和，相互卷積也是積性函數。

1.f(1)=1。

2.性質一：對于n=∏pi^ki，有f(n)=∏f(pi^ki)

性質二：對于完全積性函數，還有f(n)=∏f(pi)^ki以及f(n^k)=f(n)^k

常見的積性函數：

1.d(n)=Σ_d|n?1，表示n的因子個數，即d=1*1

2.σ(n)=Σ_d|n d，表示n的因子和，即σ=1*id

3.1(n)=1，恒等函數

4.id(n)=n，單位函數

5.e(n)=[n=1]，元函數，即f=f*e

6.φ(n)=Σ[(n,i)=1]*1，歐拉函數

φ*1=id

7.μ(n)，莫比烏斯函數，μ(n)=(-1)^k，k為n的素因子個數，有重復素因子時μ=0

μ*1=e

?

【狄利克雷卷積】

定義兩個數論函數f,g的狄利克雷卷積：(f*g)(n)=Σ_d|nf(d)*g(n/d)。

1.莫比烏斯函數，e(n)=Σ_d|nμ(d)，即e=μ*i。

莫比烏斯反演，由g=f*i，得f=g*μ。（可以看出μ和1互為逆元）

證明：f=g*μ=f*i*μ=f*e=f。

即由g(n)=Σ_d|nf(d)，得f(n)=Σ_d|ng(d)*μ(n/d)。

類似的，由g(n)=Σ_n|df(d)，得f(n)=Σ_n|dg(d)*μ(d/n)。

$$\sum_{d|n}\mu(d)=[n=1]\ \ (\mu \times 1=e)$$

2.歐拉函數，n=Σd|nφ(d)，即id=φ*i。

$$\sum_{d|n}\varphi(d)=n\ \ (\varphi \times 1=id)$$

證明：考慮n的所有數字x∈[1,n]，有(n,x)=d即(n/d,x/d)=1，所以滿足(n,x)=d的所有的x的個數為φ(n/d)，那么所有n的因子的φ就是答案。

由反演得，φ=id*μ，即φ(n)/n=Σ_d|nμ(d)/d。

$$\varphi(n)=\sum_{d|n}\frac{n}ze8trgl8bvbq*\mu(d)\ \ (\mu \times id=\varphi)$$

公式：1~n中與n互質的整數和是為( n*φ(n)+[n=1] )/2，證明：gcd(n,i)=gcd(n,n-i)，所以互素數總是成對出現。（但約數和不是n*(n+1)/2-n*φ(n)/2+1……）。

★莫比烏斯反演

?

【和式Σ變換技巧】

基本法則（具體數學）：

1.分配律，Σ_kc*a_k=c*Σ_ka_k，即提出與Σ無關的乘數。

2.結合律，將相鄰Σ的條件結合或分離。

3.交換律，即Σ的枚舉可以改變順序。

4.一般分配律，Σ_j,ka_j*b_k=(Σa_j)*(Σb_k)

5.多重交換律，當相鄰Σ枚舉域相關時，需滿足：

[j∈J][k∈K(j)]=[k∈K'][j∈J'(k)]

通常J=K'是所有整數集合，第二重根據操控二重和式性質的p(j,k)推出。

6.換元，即更換Σ的枚舉元。

7.艾弗森約定，即將Σ底端限制變成條件，如Σ_i∈Ii = Σi*[i∈I]。

【杜教篩】

參考：淺談一類積性函數的前綴和?by?skywalkert

給定數論函數$f(n)$，求$s(n)=\sum_{i=1}^{n}f(i)$。

考慮找到一個合適的數論函數$g(n)$。

杜教篩基本變化（總值與倍數互換）

$$\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}ze8trgl8bvbq)=\sum_{i=1}^{n}g(i)s(\frac{n}{i})$$

最終

$$g(1)s(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)s(\frac{n}{i})$$

本質上是構造卷積h=f*g，若h和g的前綴和可以O(1)或O(√n)快速求解，則可以用上式快速求解f的前綴和。

最后將f的前n^(2/3)項預處理，總復雜度O(n^(2/3))。

求N和N/i時，s(i)記憶化到f[N/i]中，f[]數組大小只需要√N。（N變化時要清空數組）

例題：【51nod】1239 歐拉函數之和?求Σφ(i)

?

復雜度證明：

根據(x/a)/b=x/(ab)，杜教篩只用到2√n個值，所以杜教篩的復雜度是：

$$\sum_{i=1}^{\sqrt n}O(\sqrt i)+\sum_{i=1}^{\sqrt n}O(\sqrt{\frac{n}{i}})$$

計算復雜度需要用到積分：

$$\int_{0}^{a}x^n=\frac{1}{n+1}a^{n+1}$$

所以，前半部分的復雜度：

$$\sum_{i=1}^{\sqrt n}O(\sqrt i)=\int_{0}^{\sqrt n}x^\frac{1}{2}\approx \sqrt n^{\frac{1}{2}+1}=O(n^{\frac{3}{4}})$$

后半部分的復雜度：（把√n提出來，最后是n^(3/4)）

$$\sum_{i=1}^{\sqrt n}O(\frac{1}{\sqrt i})=\int_{0}^{\sqrt n}x^{-\frac{1}{2}}\approx \sqrt n^{-\frac{1}{2}+1}=O(n^{\frac{1}{4}})$$

最終，復雜度$O(n^{\frac{3}{4}})$，預處理前2/3項后復雜度為$O(n^{\frac{2}{3}})$。（這暫時不太清楚）

?

轉載于:https://www.cnblogs.com/onioncyc/p/8461267.html

總結

以上是生活随笔為你收集整理的【算法专题】积性函数的全部內容，希望文章能夠幫你解決所遇到的問題。

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