Codeforces Round #681 题解

Div2 A / Kids Seating

题目链接

题意简述

给定一个数 (n)，要求构造出一个长度为 (n) 的数列 (A) ，满足对于任意两个数，这两个数两两不互质且互相不为对方的倍数，并满足(1leq A_ileq 4 imes n) 。

题解

显然，如果想让这些数不互质，令这些数都为 (2) 的倍数可以使这些数就可能小。并且我们注意到，对于任意 (i,jin[n+1, 2 imes n])且 (i ot= j)，有 (2 imes i) 与 (2 imes j),满足题目中的条件。于是我们就显然想到了构造方法，即对于一个 (n)，构造出的序列为 (4 imes n,4 imes n-2， ……,2 imes n +2)。复杂度 (O(n))。

代码

#include<bits/stdc++.h>
using namespace std;
int a[110];
int p[110],cnt=0,flag=1;
int n,t;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int cnt=1;
		for(int i=4*n;cnt<=n;cnt++,i-=2)
			printf("%d ",i);
		puts("");
	}
}