發表新討論
#85: 請問找因數有沒有什麼技巧?


tim37021 (SDMOGRFSIS)

學校 : 桃園市立中興國民中學
編號 : 1134
來源 : [140.116.247.193]
最後登入時間 ：
2017-02-24 15:53:47
b081. B. 友好數 -- 2007 NPSC 國中組決賽 | From: [59.121.61.219] | 發表日期 : 2007-12-25 21:14

我用迴圈慢慢跑會TLE(我的程式要跑9X秒)，

有什麼技巧嗎，

我看到有人只跑7XXms

 
#87: Re:請問找因數有沒有什麼技巧?


looser (looser)

學校 : 不指定學校
編號 : 1031
來源 : [122.121.26.214]
最後登入時間 ：
2008-11-01 03:37:57
b081. B. 友好數 -- 2007 NPSC 國中組決賽 | From: [220.129.64.228] | 發表日期 : 2007-12-26 08:25

我用迴圈慢慢跑會TLE(我的程式要跑9X秒)，

有什麼技巧嗎，

我看到有人只跑7XXms

假設n 找1~sqrt(n) 的範圍就可以把所有的因數找出來.這題n=10^6.sqrt(n)=10^3...所以很快便能完成找因數的步驟.

 
#88: Re:請問找因數有沒有什麼技巧?


tim37021 (SDMOGRFSIS)

學校 : 桃園市立中興國民中學
編號 : 1134
來源 : [140.116.247.193]
最後登入時間 ：
2017-02-24 15:53:47
b081. B. 友好數 -- 2007 NPSC 國中組決賽 | From: [59.121.47.190] | 發表日期 : 2007-12-26 21:53

假設n 找1~sqrt(n) 的範圍就可以把所有的因數找出來.這題n=10^6.sqrt(n)=10^3...所以很快便能完成找因數的步驟. 

哇!真的好快阿

我跑了296ms，完全無誤!!

謝謝你嚕!

學到一招

 
#110: Re:請問找因數有沒有什麼技巧?


linishan (L)

學校 : 國立交通大學
編號 : 1090
來源 : [104.132.150.102]
最後登入時間 ：
2019-05-10 19:57:54
b081. B. 友好數 -- 2007 NPSC 國中組決賽 | From: [218.168.68.11] | 發表日期 : 2008-01-13 10:26

假設n 找1~sqrt(n) 的範圍就可以把所有的因數找出來.這題n=10^6.sqrt(n)=10^3...所以很快便能完成找因數的步驟. 

 哇!真的好快阿

我跑了296ms，完全無誤!!

謝謝你嚕!

學到一招



也可以使用輾轉相除法

速度一樣快

 
ZeroJudge Forum