[Codeforces Round #447][Codeforces 894C]Marco and GCD Sequence

    题意：有一正整数数列\(\{a_n\}\)，把所有的\(gcd(a_i,a_{i+1},a_{i+2},\ldots,a_j),1<=i<=j<=n\)加进集合S中。给出集合S，求原正整数序列。其中\(|S|<=1000\)，且要求输出的数列长度<=4000。

    题解：考虑这类构造题时一种很有效的构造方法是将原数列中所有数在不删除的情况下全部加进构造的数列中。考虑无解的情况，如果原数列中所有数的gcd不等于原数列中最小的数，那么一定是无解的。接下来考虑在仅排除这种情况能否构造出一组解。一个较好的构造方法是\(a_1\ a_2\ a_1\ a_3\ a_1\ a_4\ a_1\cdot\ a_n\)。

#include <bits/stdc++.h>
using namespace std;
const int maxn=4010;

int a[maxn];
int n;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for (int i=2;i<=n;i++) if (a[i]%a[1])
	{
		printf("-1\n");
		return 0;
	}
	if (n==1)
	{
		printf("1\n%d\n",a[1]);
		return 0;
	}
	printf("%d\n",(n-1)*2);
	for (int i=2;i<=n;i++)
	{
		printf("%d %d ",a[1],a[i]);
	}
	printf("\n");
	return 0;
}