#2398: 該怎麼加速...
smartkevingenius
(密碼是我的班級座號 加油吧學弟妹)
學校
:
臺北市立忠孝國民中學
編號 : 7143
來源 : [180.176.124.57]
最後登入時間 ：
2016-03-08 09:08:54
d446. 生成因數
| From: [124.8.83.242] |
發表日期
:
2009-09-19 23:45
我從1找到sqrt(n)
把答案都存在一個字串裡
但還是超過5S
可以請通過的大大教一下
有什麼更快的方法嗎
#2399: Re:該怎麼加速...
d446. 生成因數
| From: [118.161.218.236] |
發表日期
:
2009-09-20 07:17
我從1找到sqrt(n)
把答案都存在一個字串裡
但還是超過5S
可以請通過的大大教一下
有什麼更快的方法嗎
liouzhou_101說道
少用內建函式為妙 ， 反正都是跑到sqrt(n) ，何不找一個變數代替....
補充 : 也許也會有人用i*i<=n 不過在此題 貌似無法通過 (連乘法也太慢了!)
以上為上秒的作法
以下為200ms的作法
先做因數分解，之後跑樹枝狀，再加上快排
雖然做因數分解有一些成本 (5萬以內約5200質數)
最多跑個5200+因數個數+快排成本 <=sqrt(n)
最多跑個5200+因數個數+快排成本 <=sqrt(n)
#16564: Re:該怎麼加速...
ZeroJudge Forum