#P13687. [ARC122E] Increasing LCMs

    ID: 12889 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高逆向思考欧几里得算法最小公倍数排列构造

[ARC122E] Increasing LCMs

题目描述

有一个长度为 NN 的正整数序列 A1,A2,⋯ ,ANA_1,A_2,\cdots,A_N。你可以通过重新排列这些整数,构造一个正整数序列 x1,x2,⋯ ,xNx_1,x_2,\cdots,x_N。此时,xx 需要满足以下条件:

  • 定义 yi=LCM⁡(x1,x2,⋯ ,xi)y_i=\operatorname{LCM}(x_1,x_2,\cdots,x_i),其中 LCM⁡\operatorname{LCM} 表示给定整数的最小公倍数。此时,yy 必须严格单调递增。也就是说,y1<y2<⋯<yNy_1 < y_2 < \cdots < y_N 必须成立。

请判断是否存在满足条件的 xx,如果存在,请给出一个例子。

输入格式

输入以以下格式从标准输入读入:

NN A1A_1 A2A_2 ⋯\cdots ANA_N

输出格式

如果存在满足条件的 xx,请按以下格式输出答案:

Yes x1x_1 x2x_2 ⋯\cdots xNx_N

如果不存在,输出 No。

输入输出样例 #1

输入 #1

3
3 4 6

输出 #1

Yes
3 6 4

输入输出样例 #2

输入 #2

3
2 3 6

输出 #2

No

输入输出样例 #3

输入 #3

10
922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247

输出 #3

Yes
922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857

说明/提示

限制

  • 1≤N≤1001 \leq N \leq 100
  • 2≤A1<A2<⋯<AN≤10182 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}
  • 输入的所有值均为整数。

样例解释 1

当 x=(3,6,4)x=(3,6,4) 时,

  • y1=LCM⁡(3)=3y_1=\operatorname{LCM}(3)=3
  • y2=LCM⁡(3,6)=6y_2=\operatorname{LCM}(3,6)=6
  • y3=LCM⁡(3,6,4)=12y_3=\operatorname{LCM}(3,6,4)=12 因此满足 y1<y2<y3y_1 < y_2 < y_3。

样例解释 2

无论如何排列 AA,都无法满足条件。