我說一下我的想法，不好或不對請各位強者不吝指正 如果對題意沒理解錯… (事實是，我讀了你的程式碼才了解何謂 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