在数论中的积性函数。对于正整数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