Mashmokh and Numbers CodeForces - 415C

时间:2022-07-10 18:14:17

题意:就是n个数和k,每次按顺序那两个数,最大公约数的和为k。

思路:注意:当n=1,k>0时一定不存在,还有n=1,k=0时为1即可。

   然后再正常情况下,第一组的最大公约数为k-n/2+1即可,后面是含有素数。(本来,配的是素数和素数+1, 然后会怕第一组会重复,后来直解两个素数了,因为第一组要么是特殊的素数要么是合数所以么有必要担心重复)

#include<iostream>
using namespace std;
#define N int(1e7+10)
int prime[N]; //第i个素数是prime[i]
bool vis[N]; //表示i是否是被筛过(素数的倍数会提前被筛去)
bool is_prime[N];//true表示是素数
int Prime(int n)
{
int cnt = ;
for (int i = ; i <= n; ++i)
{
if (!vis[i])
{
prime[cnt++] = i;
is_prime[i] = ;//表示是素数
}
for (int j = ; j < cnt&&i*prime[j] <= n; ++j)
{
vis[i*prime[j]] = ;
if (i%prime[j] == )break; //这里就避免了 例子:6,在2就被筛去,避免了还要经过3又筛一遍。
}
}
return cnt;
}
int num[N];
int main()
{
int cnt = Prime(N);
int n, k;
scanf("%d%d", &n, &k);
int t = n / ;
if (n == && k == )printf("1\n");
else if (k < t || n < )printf("-1\n");
else{
printf("%d %d", (k - t + ) * , (k - t + ) * );
for (int i = ; i <= n; ++i)
printf(" %d", prime[i]);
}
}