首先，我們必須弄清楚什麼是積性函數：
在非數論領域，積性函數是指所有對于任何a和b都有性質f(ab)=f(a)f(b)的函數。 在數論領域，考慮一個函數值為正整數的函數f，對于任意兩個互質的正整數a和b，均滿足f(ab)=f(a)f(b)，則函數f稱為積性函數。假如對于任意兩個正整數a和b，都有f(ab)=f(a)f(b)，則函數f也稱為完全積性函數。 容易看出，對于任意積性函數（包括完全積性函數），f(1)=1。
由于任何一個大于1的自然數n都可以唯一分解成有限個質數的乘積，是以積性函數f(n)的值完全由質數的幂決定。也就是說，若将n表示成質因子分解式n=Πpaii，其中pi為互不相同的質數，那麼對于一個積性函數f，f(n)=f(Πpaii)=Π f(paii)。如果f還滿足完全積性，則f(n)= Π f ai(pi)。
下面介紹數論中兩個常見的積性函數：
1)歐拉函數φ(n)，用于計算與n互質的正整數個數。
2)莫比烏斯函數μ(n)，用于計算非平方數n的質因子個數，μ(n)為φ(n)的反演函數。
3.3.1 使用歐拉函數φ(n)計算與n互質的正整數個數
歐拉函數φ(n)表示{1，…，n}中與n互質的整數個數。例如，φ(1)=φ(2)=1，φ(3)=φ(4)=2。
當n是素數時，φ(n)=n-1。
當n是合數時，φ(n)若m、n互質，φ(mn)=φ(m)φ(n)。
顯然，φ(n)為積性函數，但不是完全積性函數。
考慮一個質數p和正整數k，不難看出φ(pk)=pk-pk-1=(p-1)pk-1。
在數論中，歐拉定理具有一個關于同餘的性質。
歐拉定理：若n和a為正整數且n和a互質（gcd(a，n)=1），則aφ(n)≡1 (mod n)。
證明：
首先證明下面這個命題：
對于集合zn={x1,x2,...,xφ(n)},其中xi是不大于n且與n互素的數(1≤i≤φ(n))，即n的一個化簡剩餘系(或稱簡系，或稱縮系)。考慮集合s={ ax1(mod n),ax2(mod n),...,a*xφ(n)(mod n)}，則s=zn。
1)由于a、n互質，xi也與n互質，則axi也一定與n互質，是以對于任意xi，axi(mod n) 必然是zn的一個元素。
2)對于zn中兩個元素xi和xj，如果xi≠xj，則axi(mod n) ≠ axj(mod n)，這個由a、n互質和消去律可以得出。
是以，很明顯，s=zn。
既然這樣，那麼 （ax1ax2…axφ(n)）(mod n)
=(［aφ(n)］x1x2…xφ(n))(mod n)
=（(ax1(mod n))(ax2(mod n))…(axφ(n)(mod n))）(mod n)
=（x1x2…xφ(n)）(mod n) 考慮等式 (［aφ(n)］x1x2…xφ(n))(mod n)=（x1x2…xφ(n)）(mod n)。由于x1x2…*xφ(n)與n互質，是以根據消去律可從等式兩邊約去，于是得到歐拉定理aφ(n)≡1(mod n)。
推論：對于互質的數a、n，滿足aφ(n)+1≡a(mod n) 。
歐拉定理的一個特例是費馬定理。
費馬定理：假如p是質數且a與p互質，則 ap-1 ≡1(mod p)。另一種形式是，設p是素數, 則對任意的整數a，ap≡a(mod p)。
證明費馬定理非常簡單，隻要将φ(p)=p-1代入歐拉定理aφ(n)≡1(mod n)即可證明。在a能被p整除時，ap≡a(mod p)的結論顯然成立。費馬定理提供了一種不用因子分解就能斷定一個數是合數的新途徑。例如29-1≡4(mod 9),可以斷定9是合數。
歐拉函數有兩個重要性質：
性質1：∑dnφ(d)=n。
性質2：當n>1時， 1…n中與n互質的整數和為nφ(n)2。
下面給出歐拉函數的程式示例：
歐拉函數可應用于許多具有積性性質的數論問題。例如:
1)設對質數p取模意義下n的乘法逆元為f(n)，現在要求出f(1)、f(2)、…、f(n)。
解法：很容易看出f是完全積性函數，這樣如果對于質數p求出了f(p)的值，任意f(n)就能求出了。是以可采用線性篩法求逆元。用擴充歐幾裡得算法求一次乘法逆元的時間複雜度為o(log2n)，而質數的個數正好為nlog2n，是以這個算法的時間複雜度為o(n)。其實這個問題并沒有這麼麻煩。設p=nt+k，則f(n)=(nt2*f(k)2)mod p。
證明過程如下：∵nt≡-k(mod p)→ntf(k)≡-1(mod p)→n2t2f(k)2≡1(mod p)
∴n-1≡nt2f(k)2(mod p)顯然，由于1≤k2)求c(n，m)mod p，其中0≤m≤n≤106，p為大質數。
解法：根據c(n，m)=n!m!(n-m)!，可以用時效為o(m*log2m)的“蠻力算法”求解。其實這題可以利用預處理（預先計算n!-1）加速計算。由逆元的積性，可得n!-1≡∏nk=1k!－1≡∏nk=1f(k)%p這樣也就能線性預處理階乘的逆元了。這個算法能在某些組合計數問題中派上用場。
由于歐拉函數的程式基本上是模式化的，是以解題的關鍵是如何将數論問題抽象成計算與n同質的正整數個數的數學模型。隻要能夠抽象出相應的數學模型，程式編寫就變得輕而易舉了。
【3.3.1.1 relatives】
【問題描述】
給出一個正整數n，有多少個小于n的正整數是對于n的相對素數？如果不存在整數x>1、y>0、z>0使得a=xy，且b=xz，則兩個整數a和b是相對素數。
輸入：
給出若幹測試用例。每個測試用例占一行，給出n≤1000000000。在最後一個測試用例後的一行給出0。
輸出：
對每個測試用例輸出一行，給出上述問題的答案。
試題來源：waterloo local 2002.07.01
線上測試位址：poj 2407，zoj 1906，uva 10299
試題解析
n的相對素數的個數為歐拉函數φ(n)，這個函數為積性函數，即n若分解出k個素數乘幂形式n=pe11 pe22…pekk，則φ(n)=φ(p1)φ(p2)…φ(pk)其中φ(pi)=(pi-1)pei-1i（1≤i≤k）程式清單
【3.3.1.2 primitive roots】
我們稱整數x(0請編寫一個程式，給出任何一個奇素數3≤p<65536，輸出p為模的本原根的數目。
每行輸入給出一個奇素數p，輸入以eof結束。
對每個p，輸出一行，給出一個整數，給出本原根的數目。
試題來源：賈怡@pku
線上測試位址：poj 1284
由本原根的定義可以看出，整數x（0令g為本原根，當且僅當gi能周遊n的縮剩餘系（與n互素的剩餘系），n的縮剩餘系與乘法運算構成了一個φ(n)階的循環群。
假設現有一個n階的循環群，g為這個群的一個生成元。若gk也為此群的生成元，則有(gk)m=g1 ，k*m≡1(mod n)，即m的方程有解當且僅當gcd(k，n)=1。顯然，n階的循環群的生成元共有φ(n)個。由此得到結論：
若n存在本原根，則其共有φ(φ(n))個本原根。由于題目中p為素數，p一定存在本原根，且φ(p)=p-1，是以答案就是φ(p-1)。
程式清單
3.3.2 使用莫比烏斯函數μ(n)計算非平方數n的質因子個數
若f(n)為積性函數，則函數g(n)= ∑dnf(d)也是積性函數。根據積性函數的性質，函數h(n)=f(n)g(n)為積性函數，反之亦然。由此得出莫比烏斯反演公式：f(n)= ∑dnμ(d)g(nd)其中μ是一個定義域為n的積性函數：
μ(1)=1。
當n存在平方因子時，μ(n)=0。
當n是素數或奇數個不同素數之積時，μ(n)=-1。
當n是偶數個不同素數之積時，μ(n)=1。
圖3.3-1給出了μ(n)的前50個值：1,-1,-1, 0,-1,1,-1, 0, 0, 1,-1, 0,-1, 1, 1, 0,-1, 0,-1, 0, 1, 1,-1, 0, 0,…。
由此得出∑dnμ(n)=1n=1
0其他狀況下面給出莫比烏斯函數的程式示例：
利用莫比烏斯反演可以求得歐拉函數。設f(n)=∑dnφ(d)。根據歐拉函數性質可知f(n)=n，又有φ(n)= ∑dnμ(d)f(nd)，是以φ(n)= ∑dnμ(d)nd。
莫比烏斯反演利用的是偏序集上的容斥原理。我們從另一個角度來了解一下上述公式：考慮不超過n的正整數k，根據歐拉函數的定義，我們要算出有多少k與n互質。
令gcd(n，k)=d，當d>1要被去除，考慮質數集合p={2,3,5,7,11,13…}，d>1時顯然會是p中某些質數的倍數。若p|d，可知滿足這樣條件的k有np個。這些是需要去掉的，但很容易發現中間有重複；繼續考慮兩個不同質數p1、p2，若p1p2|d，則這樣的d被重複去掉兩次，需要加上np1p2；接着考慮三個不同質數p1、p2、p3，若p1p2p3|d，在開始時被去掉三次，但是前面考慮兩個質數時又被加回三次，是以需要再去掉np1p2p3。
依此類推，考慮t個不同的質數p1、p2、p3、…、pt，若p1p2p3…pt|d，根據容斥原理，需要加上(－1)tnp1p2p3…pt。
最後觀察莫比烏斯函數定義和φ(n)= ∑dnμ(d)nd，可以發現d其實就表示若幹不同質數的乘積（若不是這樣的，μ(d)=0）。
求解積性函數一般采用線性篩法。積性函數的關鍵是如何求f(pk)。觀察線性篩法中的步驟，篩掉n的同時還得到了它的最小質因數p，我們希望能夠知道p在n中的次數，這樣就能利用f(n)=f(pk)f(npk)求出f(n)。
令n=pm，由于p是n最小的質因數，若p2|n，則p|m，并且p也是m的最小質因數。這樣在進行篩法的同時，記錄每個合數最小質因數的次數，就能算出新篩去合數最小質因數的次數。但是這樣還不夠，我們還要能夠快速求f(pk)，這時一般就要結合f函數的性質考慮。 例如歐拉函數φ，φ(pk)=(p-1)pk-1，是以進行篩法時，如果p|m，就乘上p，否則乘上p-1。再比如莫比烏斯函數μ，隻有當k=1時μ(pk)=-1；否則μ(pk)=0。與歐拉函數一樣，根據m是否被p整除進行判斷。
【3.3.2.1 能量采集】
棟棟有一塊長方形的地，他在地上種了一種能量植物，這種植物可以采集太陽光的能量。在這些植物采集能量後，棟棟再使用一個能量彙集機器把這些植物采集到的能量彙集到一起。
棟棟的植物種得非常整齊，一共有n列，每列有m棵，植物的橫豎間距都一樣，是以對于每一棵植物，棟棟可以用一個坐标(x, y)來表示，其中x的範圍是1～n，表示是在第x列，y的範圍是1～m，表示是在第x列的第y棵。
由于能量彙集機器較大，不便移動，棟棟将它放在了一個角上，坐标正好是(0, 0)。
能量彙集機器在彙集的過程中有一定的能量損失。如果一棵植物與能量彙集機器連接配接而成的線段上有k棵植物，則能量的損失為2k+1。例如，當能量彙集機器收集坐标為(2, 4)的植物時，由于連接配接線段上存在一棵植物(1, 2)，則産生的能量損失為3。注意，如果一棵植物與能量彙集機器連接配接的線段上沒有植物，則能量損失為1。現在要計算總的能量損失。
圖3.3-2給出了一個能量采集的例子，其中n=5、m=4，一共有20棵植物，在每棵植物上标明了能量彙集機器收集它的能量時産生的能量損失。
在這個例子中，總共産生的能量損失為36。
【輸入格式】
輸入檔案energy.in僅包含一行，為兩個整數n和m。
【輸出格式】
輸出檔案energy.out僅包含一個整數，表示總共産生的能量損失。
【資料規模和約定】
對于10%的資料：1≤n,m≤10。
對于50%的資料：1≤n,m≤100。
對于80%的資料：1≤n,m≤1000。
對于90%的資料：1≤n,m≤10000。
對于100%的資料：1≤n,m≤100000。
【運作時限】1秒。
【運作空限】512m。
試題來源：noi 2010
試題給出了n、m，要求計算出∑nx=1∑my=1gcd(x,y)的值(n,m≤106 )。首先，我們不難看出每個點(x,y)到(0,0)的連線上共有gcd(x,y)-1個點，這樣每個點對答案的貢獻為2(gcd(x,y)-1)+1= 2gcd(x,y)-1。顯然，最終答案為2∑nx=1∑my=1gcd(x,y)-nm。
計算的瓶頸在于如何快速算出∑nx=1∑my=1gcd(x,y)，蠻力枚舉顯然會逾時。
令t=gcd(x,y)，換一個角度，枚舉t所有可能的值，計算每個t值下有多少數對{(x，y)|x≤n，y≤m，gcd(x，y)=t}，也就是計算有多少個數對{(x，y)|x≤nt，y≤mt，gcd(x，y)=1}。令n′=nt，m′=mt，f(t)={(x,y)x≤n′,y≤m′,gcd(x,y)=tf(t)表示該範圍内滿足gcd(x，y)=t的數對個數。顯然f(t)也不是那麼容易求出的。再考慮一個函數g(t)={(x,y)x≤n′,y≤m′,gcd(x,y)=kt,k∈z+g(t)表示該範圍内滿足gcd(x，y)為t的倍數的數對個數。我們可以很容易得到以下結論：g(t)=n′t mt再考慮g(t)與f(t)之間的關系，顯然有g(t)=∑tkf(k)。注意到g函數的值是很容易求出的，而f函數的值卻非常不易求得。我們不妨對其做莫比烏斯反演f(t)=∑tkgktμ(k)。由于我們要求的是f(1)，可得f(1)=∑kg(k)*μ(k)。
這樣，我們就得到了計算互質對數的公式。然而如果蠻力枚舉t和k，顯然也是平方級的時間複雜度，同樣會逾時。下面考慮如何繼續優化：
首先，很容易看出nt的取值隻有2n種，同理mt的取值隻有2m種，并且相同取值對應的t是一個連續的區間，是以nt和mt都相同的區間最多隻有2n+2m個，這樣t的枚舉量就縮小為o(n+m)了。如果使用線性篩法預處理μ函數的部分和，總的時間複雜度就減至o(n+m)，可見其效率非常高。