UVa 294 Divisors

這題的加速關鍵就在於質因數分解

例如 360 = 2^3 + 3^2 + 5
那麼360的因數個數就是(3+1)*(2+1)*(1+1)

其實作到質因數分解就可以在UVa拿到AC了
不過ZeroJudge的測資顯然要嚴酷許多
所以我建了質數表增加質因數分解的效率。

我解題時相當程度上參考了Sagit's code
http://www.tcgs.tc.edu.tw/~sagit/acm/view.php?id=294
簡潔易讀的寫法,相當佩服

這題我還有個心得就是gcc -O2 這個參數
對vector的速度影響非常大
我跑這個測資
1
999990000 1000000000
不加-O2: 3.5 sec
有加-O2: 0.8 sec
加了O2後就極為逼近原生array的速度,幾乎看不出效能損失
只要有O2,我以後就可以開心的用vector啦 :D

留言

這個網誌中的熱門文章

UVa 10125 Sumsets

讀書心得: 撒哈拉的故事

讀書心得: 你以為你以為的就是你以為的嗎?