3321. 神秘高塔
摘要
Title: 3321. 神秘高塔
Tag: 二分、线性筛
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3321. 神秘高塔
-
题意
传说这座谜题与质数有关，塔外的数学爱好者们纷纷前来挑战。他们需要在给定的区间 [a,b] 中找到最小的正整数 l ，使得在区间 [a,b] 中任意长度为 l 的连续子区间中，至少有 k 个质数。只有当他们解开了这道谜题，才能获得进入高塔的钥匙，探索塔内的宝藏。
-
思路
打出质数表，二分答案即可
-
代码
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88'''
Author: NEFU AB-IN
Date: 2023-06-09 15:54:35
FilePath: \LanQiao\3321\3321.py
LastEditTime: 2023-06-09 16:10:50
'''
# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
class sa:
def __init__(self, x, y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
# Final
N = int(2e6 + 10)
M = 20
INF = int(2e9)
# Define
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n") # Remove when Mutiple data
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65 # A -> 0
NTL = lambda x: ascii_uppercase[x] # 0 -> A
# —————————————————————Division line ——————————————————————
st, prime = [0] * N, [0] * N
cnt = 0
def init():
global cnt
st[0] = st[1] = 1
for i in range(2, N):
if st[i] == 0:
prime[cnt] = i
cnt += 1
j = 0
while i * prime[j] < N:
st[i * prime[j]] = 1
if i % prime[j] == 0:
break
j += 1
for i in range(1, N):
st[i] += st[i - 1]
init()
a, b, k = read()
if k > b - a + 1:
print(-1)
exit(0)
def check(x):
for i in range(a, b + 1):
l, r = i, i + x - 1
if r > b:
break
if st[r] - st[l - 1] > (r - l + 1) - k:
return False
return True
l, r = 1, b - a + 1
while l < r:
mid = l + r >> 1
if check(mid):
r = mid
else:
l = mid + 1
if check(l):
print(l)
else:
print(-1)