我说一下我的想法，不好或不对请各位强者不吝指正 如果对题意没理解错… (事实是，我读了你的程式码才了解何谓 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