高中生程式解題系統

#2398: 該怎麼加速...

smartkevingenius (密碼是我的班級座號加油吧學弟妹)

學校: 臺北市立忠孝國民中學

編號: 7143

來源: [180.176.124.57]

註冊時間:

2009-07-03 20:54:43

最後登入時間:

2016-03-08 09:08:54

d446. 生成因數 | From: [124.8.83.242] | 發表日期: 2009-09-19 23:45

我從1找到sqrt(n)

把答案都存在一個字串裡

但還是超過5S

可以請通過的大大教一下

有什麼更快的方法嗎

| 回應文章 | 回原始文章

#2399: Re:該怎麼加速...

morris1028 (碼畜)

學校: 國立花蓮高級中學

編號: 3529

來源: [114.37.59.62]

註冊時間:

2008-10-27 16:29:17

最後登入時間:

2021-07-12 19:00:43

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)

| 回應文章 | 回原始文章

#16564: Re:該怎麼加速...

tang891228 (tang891228)

學校: 國立成功大學

編號: 61119

來源: [140.116.1.138]

註冊時間:

2016-10-16 19:30:14

最後登入時間:

2018-09-24 00:20:31

d446. 生成因數 | From: [163.32.60.239] | 發表日期: 2019-01-15 08:16

把 sqrt(n) 存到一個變數就可以了

不要每次都計算一次 sqrt(n)

| 回應文章 | 回原始文章

ZeroJudge Forum

smartkevingenius (密碼是我的班級座號 加油吧學弟妹)

morris1028 (碼畜)

tang891228 (tang891228)

smartkevingenius (密碼是我的班級座號加油吧學弟妹)