题目传送门

这道题我们只要把十进制下有七的数筛出啦就万事大吉了

类似于埃氏筛

for(int i=1;i<=10000100;i++){if(a[i])continue;if(check(i)){for(int j=i;j<=10000100;j+=i)a[j]=1;continue;}nx[ls]=i;ls=i;
}

坑点

数组开大一百左右

因为当X为时

X的下一个数会大于

AC代码

#include<bits/stdc++.h>
using namespace std;
bool a[10000115];
int n,x,nx[10000115],ls;
bool check(int x){while(x){if(x%10==7)return 1;x/=10;}return 0;
}
int main(){for(int i=1;i<=10000100;i++){if(a[i])continue;if(check(i)){for(int j=i;j<=10000100;j+=i)a[j]=1;continue;}nx[ls]=i;ls=i;}scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x);if(a[x])puts("-1");elseprintf("%d\n",nx[x]);}return 0;
}