Codeforces 894C(构造)

Codeforces 894C
题意:给出一个序列的每个区间数$gcd$的集合,求构造原序列
如果集合中所有数的$gcd$不是集合中最小值,那么无解
否则直接输出原数组,但是要记得在每个数之间插上$gcd$, 否则对于下面的数据
3
2 8 12
会出现$gcd$为4但是集合中没有的情况。

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
//cf only
#define LD "%I64d"
#define D "%d"
#define pr printf
#define sc scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
using namespace std;
int read() {int x=0;char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int m, a[1000 + 5];
void clean() {
}
void solve() {
clean();
scanf("%d", &a[1]);
int g = a[1], minn = a[1];
for (int i = 2; i <= m; i++) {
scanf("%d", &a[i]);
g = gcd(g, a[i]);
minn = min(minn, a[i]);
}
if (g != minn) {printf("-1\n"); return ;}
printf("%d\n", m + m);
for (int i = 1; i <= m; i++) printf("%d %d ", a[i], g);
}
int main() {
scanf("%d", &m), solve();
return 0;
}

------ 本文结束 ------