枚举算法再放送

再 放 送

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

练习题目

1.素数判定

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

  • 虚假的枚举

直接枚举22n1n-1的所有数,看是否能整除nn,时间复杂度O(n)O(n)

  • 真正的枚举

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

不妨设aba\le b

那么就有n=a×ba2n=a\times b\ge a^2

ana\le \sqrt{n}

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

2.Squarefree number

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

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

  • 虚假的枚举

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

  • 真正的枚举

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

显然a,ba,b不同时大于10610^6

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool square(ll x)
{
ll y=(ll)sqrt(x+0.5);
return x==y*y;
}
bool squarefree(ll x)
{
if(square(x)) return false;
for(ll i=2;i<=x/i/i;i++)
{
if(x%(i*i)==0) return false;
if(x%i==0 && square(x/i)) return false;
}
return true;
}
int main()
{
int T;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
ll x;
scanf("%lld",&x);
printf("Case %d: ",cas);
if(squarefree(x)) puts("Yes");
else puts("No");
}
}

3.Forever Young

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

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

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

  • 虚假的枚举

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

最简单的例子,比如不管nn多大,只要下届是1010,答案就可以是nn进制。

  • 真正的枚举

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

比如n=a0+a1B+a2B2+a3B3+n=a_0+a_1B+a_2B^2+a_3B^3+\dots

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,L;
int len;
int d[30];
int getlen(ll x)
{
int ans=0;
while(x)
{
++ans;
x/=10;
}
return ans;
}
bool ok(ll n,ll l,ll B)
{
int cnt=0;
while(n)
{
if(n%B>=10) return false;
d[cnt++]=n%B;
n/=B;
}
ll now=0;
for(int i=cnt-1; i>=0; --i)
now=now*10+d[i];
return now>=l;
}

int main()
{
scanf("%I64d%I64d",&n,&L);
len=getlen(L);

ll ans=10;
for(ll B=2000000; B>=10; --B)
if(ok(n,L,B))
{
ans=B;
break;
}
for(int i=0; i<10; ++i)
for(int j=0; j<10; ++j)
for(int k=0; k<10; ++k)
if(i*100+j*10+k>=L)
{
if(i==0 && j==0) assert(false);
ll l=0,r=n,mid;
while(l<r)
{
mid=(l+r+1)/2;
if(i*mid+j<=(n-k)/mid) l=mid;
else r=mid-1;
}
if(l>=10 && (n-k)%l==0 && (n-k)/l==i*l+j)
ans=max(ans,l);
}
printf("%I64d\n",ans);
}

枚举算法再放送
https://izard.space/2019/04/29/枚举算法再放送/
作者
forever_you
发布于
2019年4月29日
许可协议