题解 | Wonderprime-牛客假日团队赛5G题

G-Wonderprime Brands_牛客假日团队赛5

https://ac.nowcoder.com/acm/contest/984/G

题目描述

The cows are forever competing to see who has the best brand. The latest rage is brands that are 'Wonderprimes'. You probably already know that a brand consists of a sequence of digits that does not begin with 0; brands actually look a lot like positive integers.
A wonderprime is a number that can be partitioned into two prime numbers, each of which has at least D digits and, of course, doesn't start with 0. When D=2, the number 11329 is a wonderprime (since it connects 113 and 29, both of which are prime).
Only a few of the cows have wonderprime brands, but they all want one. Your job is to find the first wonderprime greater than or equal to a supplied integer $N (1 \leq N \leq 2,000,000,000)$ . No integer greater than 2,000,000,000 will be required.

输入描述:

Line 1: Two space-separated integers: D and N( $1 \leq D \leq 5, 1\leq N \leq 2000000000$ )

输出描述:

Line 1: A line that contains the first wonderprime no smaller than N.

示例1

输入

2 11328

输出

11329

解答

一开始预处理出素数表，写了一波后发现，要处理的数超过能处理的素数表，然后一想到其实大于某个数的素数很少复杂度就可以找到，所以就暴力找了，然后就根据前面n位刚好等于和前面n位大于两种情况去算就可以了

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 1e6+9;
const ll mod = 1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f;
 
int a[50];
 
int Find(int x){
    if(x==1)return 2;
    for(int i=x;;i++){
        int flag=1;
        for(int j=2;j*j<=i;j++){
            if(i%j==0){flag=0;break;}
        }
        if(flag)return i;
    }
}
 
ll solve(int x,int y,int p){
    ll tmp1=Find(x);
    if(tmp1==x){
        ll tmp2=Find(y);
        ll tmp=tmp2;
        ll res=x;
        while(tmp){
            res*=10;
            tmp/=10;
        }
        return res+tmp2;
    }
    else{
        ll tmp2=Find(p);
        ll res=tmp1;
        ll tmp=tmp2;
        while(tmp){
            res*=10;
            tmp/=10;
        }
        return res+tmp2;
    }
}
 
ll solve(int x,int y){
        ll tmp1=Find(x);
        ll tmp2=Find(y);
        ll res=tmp1;
        ll tmp=tmp2;
        while(tmp){
            res*=10;
            tmp/=10;
        }
        return res+tmp2;
}
 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int tmp=m;
    int num=0;
    while(tmp){
        a[num++]=tmp%10;
        tmp/=10;
    }
    int flag=0;
    ll ans=INF;
    for(int i=n;i<=num-n;i++){
        flag=1;
        int tmp1=0;
        int j;
        int t;
        for(j=num-1,t=1;j>=0;j--,t++){
            tmp1=tmp1*10+a[j];
            if(t==i)break;
        }
        int tmp2=0;
        int mm=1;
        for(j--;j>=0;j--){
            tmp2=tmp2*10+a[j];
            mm*=10;
        }
        if(tmp2==0)tmp2=mm/10;
        ans=min(ans,solve(tmp1,tmp2,mm/10));
        ans=min(ans,solve(tmp1+1,mm/10));
    }
    if(flag==0){
        int nn=1;
        for(int i=1;i<n;i++)nn*=10;
        int tmpp=Find(nn);
        printf("%d%d",tmpp,tmpp);
    }
    else{
        printf("%lld\n",ans);
    }
    return 0;
}

来源：cgtllp1