当前位置：首页 > news >正文

写作网站挣钱对比网站建设科目

news 2025/9/17 8:05:17

写作网站挣钱对比,网站建设科目,seo排名怎么样,如何提高网站的转化率目录题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数…

题目翻译

【题目描述】
你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其他任何的数字除尽.

现在给定一个正整数序列 $a,a+1,\cdots,b$ $\le b)$ , 请找出一个最小值 $l$ , 使其满足对于任意一个长度为 $l$ 的子串, 都包含 $k$ 个质数.

找到并输出符合要求的最小值 $l$ , 如果不存在符合要求的长度 $l$ , 则输出 $- 1$ .

【输入格式】

输入一行, 包含三个用空格隔开的整数 $a, b, k$ ( $\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

样例 #2

样例输入 #2

6 13 1

样例输出 #2

样例 #3

样例输入 #3

1 4 3

样例输出 #3

-1

题目简化

求一个区间内，任意长度为 $l$ 的子串中都包含 $k$ 个质数的最小 $l$ 。

题目思路

初始化一个数组存储从 $2$ 开始的所有素数。初始化后，这个数组中所有值都是 true，表示对应的数是素数。

使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来找出所有小于 $M A X$ 的素数。这个算法的主要思想是，如果一个数不是素数，那么它必定有一个因子小于或等于其平方根。因此，我们只需要检查到每个数的平方根即可。

在主循环中，读取三个输入： $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;
}