【參考】html
★淺談一類積性函數的前綴和 by skywalkert數組
任之洲數論函數.pdfapp
論逗逼的自我修養之寒假頹廢記 by jiry_2函數
杜教篩 [學習筆記]【更新中】 by Candy?post
【變化技巧總結】學習
總結下面全部知識含有的變化技巧優化
1.先枚舉gcd值。spa
2.莫比烏斯反演處理gcd，[gcd(x,y)=1]=Σd|i^d|jμ(d)，而後將d提到最前面。.net
3.★分塊取值優化，ans=Σf(d)*g(n/d)，其中g(n/d)只有2√n種取值，預處理f(d)的前綴和便可O(√n)。htm
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}{d})=\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.函數爲加法時，能夠分別統計前綴和再相加，但乘法必須一塊兒統計。
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}{d}*\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*ak=c*Σkak，即提出與Σ無關的乘數。
2.結合律，將相鄰Σ的條件結合或分離。
3.交換律，即Σ的枚舉能夠改變順序。
4.通常分配律，Σj,kaj*bk=(Σaj)*(Σbk)
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}{d})=\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}})$。（這暫時不太清楚）