2021/9/9 11:54
题意:求在给定上界范围内,公差最大的且都为素数的,等差数列。
思路:贪心和模拟,为了缩小数据范围,我们可以先将范围内的素数全部枚举出来并对其进行存储。因为题目要求公差需要最大,我们就需要思考公差什么情况下最大,当取到范围内最大素数和最小素数时,我们可以知道,如果存在符合题意等差数列,那么其公差一定是最大的,之后就是对公差进行一系列的从大到小枚举了,由于2,3都为素数我们可以知道公差是一定要大于等于1的。在思考完公差之后,就要思考,题意要求如果公差相同输出最大的首项的序列,所以我们对之前存储的素数肯定也是从大到小去枚举它,如果枚举到一组符合条件的数列,那它肯定就是符合题意的那组数列,此时直接结束循环输出答案即可。
在对公差范围进行考虑的时候,我们需要考虑一下边界情况,因为求最大公差是用(最大素数-最小素数) / (n - 1),如果n等于1时需要进行特判一下,否则就会有除法错误,当n等于1时很明显我们可以看出,符合题意的公差最大序列就是它范围内的最大素数。
题目描述
2004 年,陶哲轩(Terence Tao)和本·格林(Ben Green)证明了:对于任意大的 n,均存在 n 项全由素数组成的等差数列。例如 { 7,37,67,97,127,157 } 是 n=6 的解。本题就请你对给定的 n 在指定范围内找出一组最大的解。
输入格式:
输入在一行中给出两个正整数:n(≤10)为等差素数数列的项数; MAXP (2≤MAXP<10^5)为数列中最大素数的上界。
输出格式:
如果解存在,则在一行中按递增序输出等差最大的一组解;若解不唯一,则输出首数最大的一组解。若解不存在,则输出不超过 MAXP 的最大素数。同行数字间以一个空格分隔,行首尾不得有多余空格。
输入样例1
5 1000
输出样例1
23 263 503 743 983
输入样例2
10 200
输出样例2
199
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
bool isPrime[N];
vector<int> primes, ans;
bool is_prime(int x)
{
if(x < 2)
return false;
for(int i = 2; i <= sqrt(x); i++)
{
if(x % i == 0)
return false;
}
return true;
}
void init()
{
for(int i = 2; i <= m; i++)
{
isPrime[i] = is_prime(i);
if(isPrime[i])
primes.push_back(i);
}
}
bool judge(int x, int d, int cnt)//判断是否存在n个数满足公差为d的等差数列
{
if(!isPrime[x] || x < 2)//数列中最小的元素肯定大于等于2
return false;
if(cnt <= 1)
return true;
return judge(x - d, d, cnt - 1);
}
int main()
{
cin >> n >> m;
init();
int mPrime = primes.back();
bool flag = false;
if(n == 1)
{
cout << mPrime << endl;
return 0;
}
for(int d = (mPrime - 2) / (n - 1); d >= 1 && !flag; d--)
{
for(int k = primes.size()-1; primes[k] - (n - 1) * d >= 2; k--)//数列中最小的元素肯定大于等于2
{
if(judge(primes[k], d, n))
{
flag = true;
for(int i = 0; i < n; i++)
ans.push_back(primes[k] - i * d);
reverse(ans.begin(), ans.end());//题意要求从小到大输出
break;
}
}
}
if(flag)
{
for(int i = 0; i < n; i++)
{
cout << ans[i] << (i == n - 1 ? '\n' : ' ');
}
}
else
cout << mPrime << endl;
return 0;
}