本地测70%的数据,开o2,ccf 是开o2的 i5 7267 550ms g++8 c++14 i7 7200u 504ms g++9 c++14
希望官方能给个合理的申诉结果 luogu 7个点,每个580ms,距离时间1s还差很久
#include<bits/stdc++.h>
#define pb_(x) push_back((x));
using namespace std;
const int N = 1e7 + 100;
bool b[N + 100];
int n;
int T;
vector<pair<int,int> > t;
set<int> s;
bool judge(int x)
{
if(x % 7 == 0)
return 1;
while(x)
{
if(x % 10 == 7)
return 1;
x/=10;
}
return 0;
}
int find(int x)
{
int l = 0, r = t.size() - 1,mid,ans = -1;
if(b[x] == 0)
return x;
while(l <= r)
{
mid = l + r >> 1;
if(t[mid].first >= x)
r = mid - 1, ans = mid;
else
l = mid + 1;
}
return t[ans].second;
}
int main()
{
//freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
scanf("%d", &T);
for (long long i = 400000; i >= 1 ; i--)
{
if(judge(i))
s.insert(i),b[i] = 1;
}
for (long long i = 400000; i >= 1 ; i--)
{
if(b[i])
s.insert(i);
for (set<int>::iterator it = s.begin();it != s.end() && (long long)*it * i <= N; it++)
b[i * (*it)] = 1;
}
int q = 0,p = 0;
for (int i = 1; i <= 400000; i++)
{
if(!b[i])
p = i;
else
{
t.pb_(make_pair(p,q));
q = i + 1;
}
}
while(T--)
{
int x;
scanf("%d",&x);
if(b[x])
puts("-1");
else
{
int p = find(x + 1);
printf("%d\n",p);
}
}
}