题目描述

2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。

内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。

能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

57148679-d574-4f49-b048-775c6c07791c.jpg

自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：
e = 2.71828182845904523536028747135266249775724709369995957496696762772
4076630353547594571382178525166427427466391932003059921…
其中粗体标出的 10 位数就是答案。
本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。

样例

输入格式
输入在第一行给出 2 个正整数，分别是 L 和 K。

接下来一行给出一个长度为 L 的正整数 N。

输出格式
在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。

如果这样的素数不存在，则输出 404。

注意，原始数字中的前导零也计算在位数之内。

例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

数据范围
1≤L≤1000,
1≤K<10
输入样例1：
20 5
23654987725541023819
输出样例1：
49877

算法1

(Miller_Rabin素数测试算法)

准确性很高，估摸着99.99%的准确率 ， 可以非常快的猜出某个数是不是素数

C++ 代码

#include <iostream>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 1e9 + 10;
typedef long long LL;

int n , k;
unordered_map<long long , bool> is_prime;
int prime[25] = {2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71, 73,79,83,89 , 97 };

LL quickmul(LL a , LL b , LL p)
{
    LL res = 0;

    while(b)
    {
        if(b & 1)res = (res + a) % p;
        b >>= 1;
        a = (a + a )% p;
    }
    return res;
}

LL quickpow(LL a ,LL k ,LL p){
    LL res = 1;
    while(k)
    {
        if(k & 1)res = (1ll * res * a) % p;
        k >>= 1;
        a = (1ll * a * a) % p;
    }
    return res;
}

bool MR(LL x){
    if(x == 2)return true;
    if(x == 1)return false;
    if(!(x & 1) || !x)return false;
    LL t = x - 1;

    LL y = 0;
    while(!(t & 1))
    {
        y++;
        t >>= 1;
    }

    for(int i = 0 ; i < 10 && prime[i] <= x ; i++)
    {
        LL b = quickpow(prime[i] , t , x);

        for(int j = 0 ; j < y ; j++)
        {
            LL k = quickmul(b , b , x);
            if(k == 1 && b != 1 && b != x - 1)return false;
            b = k;
        }
        if(b != 1)return false;
    }

    return true;
}

int main()
{
    cin >> n >> k;
    string res;
    cin >> res;
    int len = res.size();
    bool flag = false;
    for(int i = 0 ; i + k<= len; i++)
    {  
        LL num = stoi(res.substr(i , k));
        if( MR(num))
        {
           // if(num == 87473)continue;
            cout << res.substr(i , k);
            flag = true;
            break;
        }
    }

    if(!flag)cout << 404 << endl;
    return 0;
}