手机在线建站,凡客网,永春网站建设,做网站 服务器目录 题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 题目简化题目思路AC代码 题目翻译
【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数#xff0c;其含义就是除了数… 目录 题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 题目简化题目思路AC代码 题目翻译
【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数其含义就是除了数字一和本身之外不能被其他任何的数字除尽.
现在给定一个正整数序列 a , a 1 , ⋯ , b a,a1,\cdots,b a,a1,⋯,b ( a ≤ b ) (a \le b) (a≤b), 请找出一个最小值 l l l, 使其满足对于任意一个长度为 l l l 的子串, 都包含 k k k 个质数.
找到并输出符合要求的最小值 l l l, 如果不存在符合要求的长度 l l l, 则输出 − 1 -1 −1.
【输入格式】
输入一行, 包含三个用空格隔开的整数 a , b , k a,b,k a,b,k ( 1 ≤ a , b , k ≤ 1 0 6 ; a ≤ b 1 \le a,b,k \le 10^{6}; a \le b 1≤a,b,k≤106;a≤b)
【输出格式】 输出一行, 为符合要求的最小值 l l l, 若不存在, 输出 − 1 -1 −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 $ , $ a1 $ , $ … $ , $ b $ $ (ab) $ . You want to find the minimum integer $ l $ $ (1lb-a1) $ such that for any integer $ x $ $ (axb-l1) $ among $ l $ integers $ x $ , $ x1 $ , $ … $ , $ xl-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 $ ( $ 1a,b,k10^{6}; ab $ ).
输出格式
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 l l 的子串中都包含 k k k 个质数的最小 l l l。
题目思路
初始化一个数组存储从 2 2 2 开始的所有素数。初始化后这个数组中所有值都是 true表示对应的数是素数。
使用埃拉托斯特尼筛法Sieve of Eratosthenes来找出所有小于 M A X MAX MAX 的素数。这个算法的主要思想是如果一个数不是素数那么它必定有一个因子小于或等于其平方根。因此我们只需要检查到每个数的平方根即可。
在主循环中读取三个输入 a a a, b b b 和 k k k。然后创建一个队列 q q q 并把 a − 1 a-1 a−1 放入队列。
接下来进行一系列操作来找出在区间 [ a , b ] \text [a, b] [a,b] 中长度为 k k k 的所有素数子序列。如果存在这样的子序列那么就更新 r e s res res 的值。
如果 q q q 的头部元素是 a − 1 a-1 a−1那么就输出 -1 \texttt -\texttt 1 -1否则输出 r e s res res。
AC代码
#include bits/stdc.h
using namespace std;
#define li long long int
#define rep(i,to) for(li i0;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;queueli 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;
} 创作不易白嫖不好各位的支持和认可就是我创作的最大动力如果喜欢我的文章给个关注吧
冰焰狼 | 文
如果本篇博客有任何错误请批评指教不胜感激
