【链接】点击打开链接

【题意】

让你选择n个数字,组成一个数组,使得这n个数字中恰好有k对,它们是互质的。

【题解】

我们可以先找出前n个质数,那么接下来的问题就转化为,凑出rest = n*(n-1)/2-k对不互质的数来.

我们先找出最大的t,且满足t*(t-1)/2 <= rest.

这里的t是两两之间都不互质的数的数目.

我们可以把我们取的n个质数中的前t个质数都乘上2.(这里我们取的n个质数要从5开始取)

这样就凑了t*(t-1)/2对不互质的数了.(它们的gcd为2)

接下来处理rest2 = rest-t*(t-1)/2的部分.

我们还是一样,把取的n个质数中的前rest2个质数都乘上3,注意这里rest2是肯定小于等于t的,然后把第t+1个质数也

乘上3.

这样这rest2个数和第t+1个数又是不互质的了.(它们的gcd都为3)

虽然这rest2个数之间也是不互质的.但是这一部分实际上已经和前t个数重合了.

所以,这rest2个不互质的数,已经在前t个质数那里算一遍了。

不会重新算一遍.

【错的次数】

【反思】

之前已经算过一次,这次不会重新算.

但是可以一个一个填剩余的了

数对问题.

666

【代码】

/*

N在const里面,可以改动;

求出2..N之间的所有质数;

放在zsb数组里面;

时间复杂度是O(N)的;

但是需要空间也是O(N)的;

*/

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <queue>

#include <iomanip>

#include <set>

#include <cstdlib>

#include <cmath>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x+1)

#define oi(x) printf("%d",x)

#define oc putchar(' ')

#define ol(x) printf("%lld",x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 2e5;//

bool iszs[N + 100];

vector <int> zsb;

int n,k;

int main()

{

	ms(iszs, true);

	rep1(i, 2, N)

	{

		if (iszs[i]) zsb.pb(i);

		int len = zsb.size();

		rep1(j, 0, len - 1)

		{

			int t = zsb[j];

			if (i*t>N) break;

			iszs[i*t] = false;

			if (i%t == 0) break;

		}

	}

	//v[0] = 2,v[1] = 3;

	ri(n), ri(k);

	k = n*(n - 1) / 2 - k;

	int t = 2;

	while (t*(t - 1) / 2 <= k) {

		t++;

	}

	t--;

	rep1(i, 2, 2 + t - 1)

		zsb[i] *= 2;

	k = k - t*(t - 1) / 2;

	if (k > 0) {

		zsb[2 + t] *= 3;

		rep1(i, 2, 2 + k - 1) zsb[i] *= 3;

	}

	rep1(i, 2, 2 + n - 1)

		oi(zsb[i]), oc;

	return 0;

}

巴特西

【CS Round #43 E】Coprime Pairs