题目链接
https://www.luogu.org/problemnew/show/CF894C
Chinese Round.英文题面略微暴力,特意发了一发翻译变得更加暴力
分析
一道思维构造题,很容易发现集合中最小的元素$x$一定要满足$x|a[i]$，$a[i]$是集合中其他的元素
为啥?
因为$gcd(a_1,a_2…a_m)$显然是那个最小的元素,那么显然上述性质成立
于是判无解就很好判了
但怎么构造一组解呢?
到这里我思维就随题面一起江化了…
官方题解比较妙就是在集合的每一个元素之前都插入那个最小的元素然后输出
这样的话对于任意$GCD(a_i..a_j)$,要么是$i==j$时其本身,这样就与集合中对应的那个元素相同,要么就是那个最小的元素
思维真的江化了…
代码
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
37
38
39
40
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <queue>
#include <iostream>
#define ll long long
#define ri register int
using std::min;
using std::max;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=10005;
const int inf=0x7ffffff;
int s[maxn];
int n,mi,x;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
read(n);
mi=inf;
for(ri i=1;i<=n;i++){
read(s[i]);
mi=min(s[i],mi);
if(i==1)x=s[i];
else if(x>s[i])x=gcd(x,s[i]);
else x=gcd(s[i],x);
}
if(x!=mi){puts("-1");return 0;}
printf("%d\n",n*2);
for(ri i=1;i<=n;i++){
printf("%d %d ",s[i],x);
}
puts("");
return 0;
}
|