目錄題目翻譯題目描述輸入格式輸出格式樣例 #1樣例輸入 #1樣例輸出 #1樣例 #2樣例輸入 #2樣例輸出 #2樣例 #3樣例輸入 #3樣例輸出 #3題目簡化題目思路AC代碼 題目翻譯 【題目描述】 你決定用素數定理來做一個調查. 眾所周知, 素數又被稱為質數，其含義就是除了數字一和本身之外不能被其 ...
目錄
題目翻譯
【題目描述】
你決定用素數定理來做一個調查. 眾所周知, 素數又被稱為質數，其含義就是除了數字一和本身之外不能被其他任何的數字除盡.
現在給定一個正整數序列 $a,a+1,\cdots,b$ $(a \le b)$, 請找出一個最小值 $l$, 使其滿足對於任意一個長度為 $l$ 的子串, 都包含 $k$ 個質數.
找到並輸出符合要求的最小值 $l$, 如果不存在符合要求的長度 $l$, 則輸出 $-1$.
【輸入格式】
輸入一行, 包含三個用空格隔開的整數 $a,b,k$ ($1 \le a,b,k \le 10^{6}; a \le b$)
【輸出格式】
輸出一行, 為符合要求的最小值 $l$, 若不存在, 輸出 $-1$.
題目描述
You've decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors.
Consider positive integers $ a $ , $ a+1 $ , $ ... $ , $ b $ $ (a<=b) $ . You want to find the minimum integer $ l $ $ (1<=l<=b-a+1) $ such that for any integer $ x $ $ (a<=x<=b-l+1) $ among $ l $ integers $ x $ , $ x+1 $ , $ ... $ , $ x+l-1 $ there are at least $ k $ prime numbers.
Find and print the required minimum $ l $ . If no value $ l $ meets the described limitations, print -1.
輸入格式
A single line contains three space-separated integers $ a,b,k $ ( $ 1<=a,b,k<=10^{6}; a<=b $ ).
輸出格式
In a single line print a single integer — the required minimum $ l $ . If there's no solution, print -1.
樣例 #1
樣例輸入 #1
2 4 2
樣例輸出 #1
3
樣例 #2
樣例輸入 #2
6 13 1
樣例輸出 #2
4
樣例 #3
樣例輸入 #3
1 4 3
樣例輸出 #3
-1
題目簡化
求一個區間內，任意長度為 $l$ 的子串中都包含 $k$ 個質數的最小 $l$。
題目思路
初始化一個數組存儲從 $2$ 開始的所有素數。初始化後，這個數組中所有值都是 true，表示對應的數是素數。
使用埃拉托斯特尼篩法（Sieve of Eratosthenes）來找出所有小於 $MAX$ 的素數。這個演算法的主要思想是，如果一個數不是素數，那麼它必定有一個因數小於或等於其平方根。因此，我們只需要檢查到每個數的平方根即可。
在主迴圈中，讀取三個輸入：$a$, $b$ 和 $k$。然後，創建一個隊列 $q$ 並把 $a-1$ 放入隊列。
接下來，進行一系列操作來找出在區間 $\text [a, b]$ 中，長度為 $k$ 的所有素數子序列。如果存在這樣的子序列，那麼就更新 $res$ 的值。
如果 $q$ 的頭部元素是 $a-1$，那麼就輸出 $\texttt -\texttt 1$，否則輸出 $res$。
AC代碼
#include <bits/stdc++.h>
using namespace std;
#define li long long int
#define rep(i,to) for(li i=0;i<((li)(to));++i)
#define pb push_back
#define sz(v) ((li)(v).size())
#define bit(n) (1ll<<(li)(n))
#define all(vec) (vec).begin(),(vec).end()
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define MP make_pair
#define F first
#define S second
#define MAX 1000500
li is_prime[MAX];
int main()
{
rep(i, MAX)if(2 <= i) is_prime[i] = true;
for(li i = 2; i * i < MAX; i++){
if(!is_prime[i]) continue;
for(li j = i * i; j < MAX; j += i) is_prime[j] = false;
}
li a, b, k;
cin >> a >> b >> k;
queue<li> q;
li res = -1;
q.push(a - 1);
for(li pos = a; pos <= b; pos++){
if(is_prime[pos]) q.push(pos);
while(k < sz(q)) q.pop();
if(sz(q) == k) res = max(res, pos - q.front() + 1);
}
if(q.front() == a - 1) cout << -1 << endl;
else cout << res << endl;
}
創作不易，白嫖不好，各位的支持和認可，就是我創作的最大動力，如果喜歡我的文章，給個關註吧！
冰焰狼 | 文
如果本篇博客有任何錯誤，請批評指教，不勝感激 ！
