題意很簡單,求出 a^b 的所有因數和。

作法也不少,這裡只講一下自己的小想法。

(1) 先建出 1~n^(1/2) 的質數表。

如果 a除完 質數表裡的所有數但 a !=1時,表示 剩下的a是個大質數,且一定只有一項。

(2) 一個簡單且重要的數學公式。

假若 n=(p1^k1) * (p2^k2) * (p3^k3) * ... <質因數分解>,

則 n的因數和 = (p1^0+p1^1+p1^2+...+p1^k1) * (p2^0+p2^1+p2^2+......+p2^k2) * ....... <等比級數乘積>

(3) 把 a 質因數分解,分別計算 等比級數 再相乘。

等比級數 O(lgn)

偶數項:

e.x: a^0 + a^1 +a^2 + a^3

提出 a^2 -> a^2*(a^0+a^1)+(a^0+a^1)

合併        -> (a^2+1) * (a^0+a^1)

遞迴計算  -> <快速冪>   <遞迴>

奇數項:

e.x: a^0 + a^1 + a^2 + a^3 + a^4

提出 a^2 -> a^2*(a^1+a^2)+(a^1+a^2)+(a^0)

合併        -> (a^2+1) * (a^1+a^2) + a^0

遞迴計算  -> <快速冪>    <遞迴>     <快速冪>

搞定。

我的code

http://codepad.org/29fbUYOx

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()