yukicoder 0012 限定された素数
問題文概要
数字 '0' から '9' を使うか否かが与えられる.
$1 \le L \le R \le 5 * 10^6$ なる $L, R$ のうち, $L$ 以上 $R$ 以下の素数に現れる数字が, ちょうど与えられた "使うか否かリスト" に一致するようなものを求め, $R-L$ の最大値を答えよ.
無ければ $-1$.
制約
特になし
解法
尺取りのようにがんばる. 素数列挙に加えて, $O(R {\rm が取りうる最大値})$.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool solve(){
static auto is_prime = sieve();
static array<int, N> t = {};
rep(n, N) if(is_prime[n]) for(int m = n; m; m /= D) t[n] |= 1<<(m%D);
int a = 0;
{
int n; cin >> n;
rep(i, n){ int x; cin >> x; a |= 1<<x; }
}
int res = -1;
for(int l = 1, r = 1; true; ){
while(l < N and (t[l] & ~a)) ++l;
if(l >= N) break;
r = l;
while(r < N-1 and (t[r+1] & ~a) == 0) ++r;
int c = 0;
REP(i, l, r+1) c |= t[i];
if(c == a) chmax(res, r-l);
l = r+1;
}
cout << res << endl;
return true;
}