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


tim37021 (SDMOGRFSIS)

b081. B. 友好數 -- 2007 NPSC 國中組決賽 | From: [59.121.61.219] | 發表日期: 2007-12-25 21:14

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

有什麼技巧嗎，

我看到有人只跑7XXms

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


looser (looser)

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)

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)

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