Re: [計程] TestGirl第9題

看板b98902HW作者sa072686 (小紅)時間14年前 (2009/10/17 22:23)推噓9(9推 0噓 6→)

留言15則, 6人參與討論串2/4 (看更多)

我說一下我的想法，不好或不對請各位強者不吝指正如果對題意沒理解錯… (事實是，我讀了你的程式碼才了解何謂 relatively prime) 那麼就是求範圍 [b, c] 之間與 a 互質的個數為何我覺得這題可以使用篩法也就是說，先找出所有 a 的質因數，再對區間 [b, c] 建表記錄每個數是否已被篩去，然後開始把所有 a 的質因數的倍數全部篩掉比如說區間是 [5, 16] a 有質因數 3 則把 6, 9, 12, 15 全部篩去，看是要最後遍歷一次整個表看有幾個沒被篩掉還是在篩去時先看，如果這數沒被篩過，就計一個，否則不計，最後便知道篩去幾個據測試 max(b, c) < 20,000,000, 詳細數據不清楚，不過兩千萬應該還開得了這樣因為篩去時是稀疏的，找所有質因數是 O(sqrt(n)) 的所以速度上應該足夠解開這一題了如果 a 不會太大，甚至可以先篩法建表再遞歸求質因數，這又是另一門技巧了在篩法預處理後可以用 O(m) 的時間得出所有質因數，m 為 a 的所有質因數次方和例如 a = 2^3 * 3^5 則 m = 3+5 = 8，基本上 m <= log2(a) 算是相當小的不過在只問一次的情形，篩法預處理求質因數個數相對吃虧希望對你有幫助 ※ 引述《Natsutaka (夏宇)》之銘言： : 2007 Hw 3-3 ( score: 5 ) : 題目如下： : http://ppt.cc/Qi8U : 我的code如下： : http://homepage.ntu.edu.tw/~b94202058/test09.c : 上傳後第5筆測資傳回錯誤訊息： : 第 5 次試驗：你的程式當掉了！>"< 原因：執行時間或記憶體用量超過限制 : 沒有通過試驗。:( : 我猜測應該是執行時間過長的問題 : 理由是我自行輸入了三組測資： : 2 2 100000000 : 2 2 1000000000 : 2 2 499999999 : 執行了很久才跑出結果 : 為了加快執行速度 : 我寫了一段code將 A = 2 的情形特別處理 : 可是還是沒有通過第5筆測資的試驗 : 現在這一段code已經被我註解起來 : 請教各位我的code或algorithm有什麼問題呢? : 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.248.145

推

s864372002

10/17 22:29, , 1^F

10/17 22:29, 1^F

推

cwahbong

10/17 23:12, , 2^F

10/17 23:12, 2^F

推

gn00499901

10/17 23:13, , 3^F

10/17 23:13, 3^F