![](https://csdnimg.cn/release/download_crawler_static/86311328/bg3.jpg)
总体的相应指标。在某些问题中,需要让我们检查一系列测试元 s,如果 s 中的
某个测试元满足了某个条件,那么则说 s 满足了某个性质。在大度数情况下,
我们需要将 s 中的测试元一个一个的进行验证,才能确定 s 是否满足该性质。但
是如果 s 满足如下性质,要不 s 中不含满足条件的测试元,要不满足某条件的测
试元很多,则可以直接选取几个具有代表性的测试元进行测试,通过这几个测
试元来确定 s 是否满足该性质。
例题 3 SPOJ919 Prime Checker
存在一个数列,第一项为 1,以后各项根据公式 a
i
=(a
i-1
+1234567890) mod
2
31
推出,问这个数列的各项是否为质数。如果是质数的就输出 0,是合数的就
输出 1,在时间限制内输出的越多,得到的分数越多。
看到这个题目,我们首先想到的是最为朴素的做法,先求出 1-100000 的素
数表,然后对于每个数 a
i
,用 1-trunc(sqrt(a
i
))间质数去除这个数,如果某个质数
能够整除 a
i
,则 a
i
为合数,如果均不能整除,则 a
i
为质数。这种方法实现起来无
疑是十分简便的,但是由于复杂度较高,所以在时间限制内仅能完成 200000 多
一点的数。
下面我们来看一个使用抽样测试法的质数判断方法。对于一个整数 n,设
n-1=d*2^s(d 是奇数),对于给定的基底 a,如果存在 a^d=1(mod n)或者对于
0<=r<s,存在 a^(d*2^r)=-1(mod n)则称 n 是以 a 为基底的强伪质数。一个质数 n
以所有小于 n 的整数为底都是强伪质数,而一个合数 n,以小于 n 的数为底,n
最多有 1/4 的机会成为强伪质数。根据这条,我们不妨随机地抽取小于 n 的数为
底,如果抽取了 k个数,则正确的概率为 1-1/4^k,k取到几十的时候一般不会出
错了。如果我们不采用随机的方法而是直接抽样特殊底——最小的几个质数,
情况怎样呢?
经过试验发现,如果以 2 为底,第一个不符合的数为 2047;如果以 2、3 为
底,第一个不符合的数为 1373653;如果以 2、3、5 为底,第一个不符合的数为
25326001;如果以 2、3、5、7 为底,则 2^31 内的数均符合了。
所以,对于本题,我们直接以 2、3、5、7 为底进行测试即可。时间复杂度
变为了 O(NlogN),比之前的朴素算法有了很多的提高。
四、模拟退火算法