← 返回题目列表

AtCoder · arc122_e

E. 增加 LCM

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

我们有一系列 N 正整数: A_1,A_2,\cdots,A_N。 你要把这些整数重新排列成另一个序列 x_1,x_2,\cdots,x_N,其中 x 必须满足以下条件:

  • 让我们定义 y_i=\operatorname{LCM}(x_1,x_2,\cdots,x_i),其中函数 \operatorname{LCM} 返回给定整数的最小公倍数。然后, y 正在严格增加。换句话说, y_1<y_2<\cdots<y_N 成立。

判断是否可以组成序列 x 满足条件,如果可能的话,显示一个这样的序列。

约束

  • 1 \leq N \leq 100
  • 2 \leq A_1 < A_2 \cdots < A_N \leq 10^{18}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N

输出

如果可以形成一个序列 x 满足条件,按以下格式打印你的答案:

Yes
x_1 x_2 \cdots x_N

如果不可能,则打印 No.


示例输入 1

3
3 4 6

示例输出 1

Yes
3 6 4

对于 x=(3,6,4),我们有:

  • y_1=\operatorname{LCM}(3)=3
  • y_2=\operatorname{LCM}(3,6)=6
  • y_3=\operatorname{LCM}(3,6,4)=12

在这里, y_1<y_2<y_3 成立。


示例输入 2

3
2 3 6

示例输出 2

No

没有排列 A 将满足条件。


示例输入 3

10
922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247

示例输出 3

Yes
922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857