枚举算法再放送

再 放 送

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一下找找：

#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(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了，实际是别的地方的问题：

#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);
}