枚举算法再放送

再 放 送

4月24日的时候我讲了程序设计与算法实践的第一课,内容包括算法时间复杂度的概念,枚举与递归等。其中关于枚举这方面还是比较有意思的,从易到难总结了三道题目枚举题,其他的内容就是老生常谈了。实际上枚举算法看似简单又不能很轻易掌握,因为枚举也是有技巧与策略的。在一道具体的题目中,暴力的枚举很可能行不通,但是聪明的枚举往往能起到“四两拨千斤”的效果。

练习题目

1.素数判定

定义一个数是素数当且仅当它是一个大于1的自然数,且不含有除1和它本身以外的因数。

  • 虚假的枚举

直接枚举2到n-1的所有数,看是否能整除n,时间复杂度\(O(n)\)。

  • 真正的枚举

考虑到如果\(n\)是合数,那么就能写成\(n=a\times b(1<a,b<n)\)的形式。

不妨设\(a\le b\)

那么就有\(n=a\times b\ge a^2\)

即\(a\le \sqrt{n}\)

也就是说如果\(n\)是合数,那么就一定有一个根号范围内的因数,所以枚举上界一下子就降下来了,时间复杂度\(O(\sqrt{n})\)。

2.Squarefree number

(题目在bnuoj上也有http://www.bnuoj.com/problem_show.php?pid=7931

给出一个数\(n(1\le n \le 10^{18})\) ,判断n的因数中有没有平方数。比如18有,21没有。

  • 虚假的枚举

直观上来看,需要枚举根号范围内的正整数\(x\),判断\(n\)是否是\(x^2\)的倍数,时间复杂度\(O(\sqrt{n})\)。

  • 真正的枚举

如果\(n\)满足条件,则一定可以表示成\(n=ab^2(b\ne 1)\)的形式。

显然\(a,b\)不同时大于\(10^6\)。

那么我们只需要分别枚举判断即可,其中枚举\(a\)时需要看除完后是否是完全平方数,这个随便搞搞就好了,总的时间复杂度\(O(n^{\frac{1}{3}})\)。

很久之前写的代码了,还是不建议直接用sqrt开方(精度误差),可以开完之后比如在加减5的范围内再for一下找找:

 

3.Forever Young

题目来源是2016 ACM-ICPC World Finals(近几年我校唯一没进总决赛的一次),当时算是第三、四道简单签到题,不过这个签到就非常有水平了。

给一个十进制数\(n(10\le y\le 10^{18})\),和一个下届\(L(10\le L)\),找到最大的正整数\(B\),使得\(n\)在\(B\)进制下只有0到9的数字,并且再当成十进制翻译后,要至少为\(L\)。

题意比较绕,还是需要结合样例理解一下。

  • 虚假的枚举

直接从大到小枚举进制\(B\),然后进制转换,验证是否符合条件,找到就退出,然而光是枚举就需要\(O(n)\),显然不行。

最简单的例子,比如不管\(n\)多大,只要下届是\(10\),答案就可以是\(n\)进制。

  • 真正的枚举

观察到一个数由更大的进制表示时,位数是越来越短的。具体来说

比如\(n=a_0+a_1B+a_2B^2+a_3B^3+\dots\)

发现当\(B>10^6\)时,\(B^3>10^{18}\),也就是说当枚举到\(B>10^6\)时,表示出来的长度不会超过3位。又因为每一位必须是0到9的数字(不能有ABCDEF这样的),那么我直接一个三层循环枚举表示后的结果,最后解一个关于B的一元二次方程\(n=a_0+a_1B+a_2B^2\)就非常trivial了。

最后把这两种枚举方式得到的答案取最大值即可,总的时间复杂度\(O(n^{\frac{1}{3}})\)。

代码写的稍微有点难看,训练的时候以为中间爆long long了,实际是别的地方的问题: