在數(shù)論中的積性函數(shù)。對(duì)于正整數(shù)n的一個(gè)算術(shù)函數(shù)f(n)，當(dāng)中f(1)=1且當(dāng)a,b互質(zhì)，f(ab)=f(a)f(b)，在數(shù)論上就稱它為積性函數(shù)。
證明： f(n) = ∑g(d)^3 (d | n, g(d)表示d的約數(shù)個(gè)數(shù)）
求證: f(n) 是積性函數(shù)，即f(1) = 1, f(ab) = f(a) * f(b); a,b互質(zhì)
(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的約數(shù)個(gè)數(shù)）
f(a) = ∑g(p)^3 (d | a, g(p)表示p的約數(shù)個(gè)數(shù)）
f(b) = ∑g(q)^3 (d | b, g(q)表示q的約數(shù)個(gè)數(shù)）
證明f(n) = f(a) * f(b)即證明∑g(d)^3 = ∑g(p)^3 * ∑g(q)^3
假設(shè) d = p * q; //d為n中的某個(gè)約數(shù)，p為a中的某個(gè)約數(shù)，q為b中某個(gè)約數(shù)，總存在d = p * q
現(xiàn)需證明g(d)^3 = g(p)^3 * g(q)^3;
g(p)^3 * g(q)^3 = (g(p) * g(q)) ^ 3
////////////////////////////////////////////
將d質(zhì)因數(shù)分解： d = p1^a1 * p2^a2 ……pj^aj
將p質(zhì)因數(shù)分解： p = p1^b1 * p2^b2 ……pj^bj
將q質(zhì)因數(shù)分解： q = p1^c1 * p2^c2 ……pj^cj
其中a1 = b1 + c1 , a2 = b2 + c2，…… aj = bj + cj;
因?yàn)閜,q互質(zhì)，所以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)是積性函數(shù)
f(n) = f(p1^a1) * f(p2 ^ a2) * f(p3 ^ a3) …… * f(pj^aj);
f(p1^a1) = ∑g(d)^3 (d | p1 ^ 3) 由p1是質(zhì)因數(shù)
所以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質(zhì)因數(shù)分解后進(jìn)行統(tǒng)計(jì)即可。（本人代碼效率不行，如果誰有更有效率的代碼麻煩給我一個(gè)，讓我學(xué)習(xí)學(xué)習(xí)）。
////////////////////////////////////////////////////////////////
轉(zhuǎn)自：http://blog.sina.com.cn/s/blog_5c95cb070100ej4c.html