在數論中的積性函數。對于正整數n的一個算術函數f(n)，當中f(1)=1且當a,b互質，f(ab)=f(a)f(b)，在數論上就稱它為積性函數。
證明： f(n) = ∑g(d)^3 (d | n, g(d)表示d的約數個數）
求證: f(n) 是積性函數，即f(1) = 1, f(ab) = f(a) * f(b); a,b互質
(1)f(1) = g(1)^3 = 1 ^ 3 = 1
(2)f(n) = f(a) * f(b);
f(n) = ∑g(d)^3 (d | n, g(d)表示d的約數個數）
f(a) = ∑g(p)^3 (d | a, g(p)表示p的約數個數）
f(b) = ∑g(q)^3 (d | b, g(q)表示q的約數個數）
證明f(n) = f(a) * f(b)即證明∑g(d)^3 = ∑g(p)^3 * ∑g(q)^3
假設 d = p * q; //d為n中的某個約數，p為a中的某個約數，q為b中某個約數，總存在d = p * q
現需證明g(d)^3 = g(p)^3 * g(q)^3;
g(p)^3 * g(q)^3 = (g(p) * g(q)) ^ 3
////////////////////////////////////////////
將d質因數分解： d = p1^a1 * p2^a2 ……pj^aj
將p質因數分解： p = p1^b1 * p2^b2 ……pj^bj
將q質因數分解： q = p1^c1 * p2^c2 ……pj^cj
其中a1 = b1 + c1 , a2 = b2 + c2，…… aj = bj + cj;
因為p,q互質，所以ai = bi + ci中要么(bi == ai && ci == 0) || (ci == ai && bi == 0)這兩種情況
g(d) = (a1 + 1) * (a2 + 1) * ……*(aj + 1);
g(p) = (b1 + 1) * (b2 + 1) * ……*(bj + 1);
g(q) = (c1 + 1) * (c2 + 1) * ……*(cj + 1);
所以g(d) = g(p) * g(q);
==> g(d)^3 = g(p)^3 * g(q)^3;
==> ∑g(d)^3 = ∑g(p)^3 * ∑g(q)^3
==> f(n) = f(a) * f(b)
從而得證f(n)是積性函數
f(n) = f(p1^a1) * f(p2 ^ a2) * f(p3 ^ a3) …… * f(pj^aj);
f(p1^a1) = ∑g(d)^3 (d | p1 ^ 3) 由p1是質因數
所以d的取值為p1^0, p1 ^ 1, p1^2, ……，p1^a1
g(p1^i) = i + 1;
故f(p1^a1) = (0 + 1) ^ 3 + (1 + 1) ^ 3 + …… + （a1 + 1) ^ 3 = (a1 + 1)^2 * (a1 + 2)^2 / 4;
以此類推，
所以最終f(n) = f(p1 ^ a1) * f(p2 ^ a2) * …… * f(pj ^ aj)
= ((a1 + 1)^2 * (a1 + 2) ^2 / 4) * ((a2 + 1)^2 * (a2 + 2)^2 / 4) * …… *
（(aj + 1)^2 * (aj + 2)^2 / 4);
將n質因數分解后進行統計即可。（本人代碼效率不行，如果誰有更有效率的代碼麻煩給我一個，讓我學習學習）。
////////////////////////////////////////////////////////////////
轉自：http://blog.sina.com.cn/s/blog_5c95cb070100ej4c.html