ACM STEPS里的…这题前面一道是求LCM….结果接下来就是这么一道。。。 朴素会超….筛法会爆….题目顺序真是按照难度来的？ 于是想到 Miller-Rabin素数测试……. 这个方法是基于费马小定理 我的理解就是… 如果我要判断n是否为素数 只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。 证明什么的…暂时还是算了吧…论文里貌似扯了一大堆 第一次用，竟然真的A了。。。。 感觉更好的办法也许是先打一个比较小的素数表，然后每次random选取若干个进行判断…那样 …