201224: [AtCoder]ARC122 E - Increasing LCMs

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $800$ points

Problem Statement

We have a sequence of $N$ positive integers: $A_1,A_2,\cdots,A_N$. You are to rearrange these integers into another sequence $x_1,x_2,\cdots,x_N$, where $x$ must satisfy the following condition:

  • Let us define $y_i=\operatorname{LCM}(x_1,x_2,\cdots,x_i)$, where the function $\operatorname{LCM}$ returns the least common multiple of the given integers. Then, $y$ is strictly increasing. In other words, $y_1<y_2<\cdots<y_N$ holds.

Determine whether it is possible to form a sequence $x$ satisfying the condition, and show one such sequence if it is possible.

Constraints

  • $1 \leq N \leq 100$
  • $2 \leq A_1 < A_2 \cdots < A_N \leq 10^{18}$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

If it is possible to form a sequence $x$ satisfying the condition, print your answer in the following format:

Yes
$x_1$ $x_2$ $\cdots$ $x_N$

If it is impossible, print No.


Sample Input 1

3
3 4 6

Sample Output 1

Yes
3 6 4

For $x=(3,6,4)$, we have:

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

Here, $y_1<y_2<y_3$ holds.


Sample Input 2

3
2 3 6

Sample Output 2

No

No permutation of $A$ would satisfy the condition.


Sample Input 3

10
922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247

Sample Output 3

Yes
922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857

Input

题意翻译

给定长度为 $N$ 的正整数序列 $\{A_i\}$,满足 $A_i$ 单调升。 问是否能将 $\{A_i\}$ 重排为序列 $\{x_i\}$,满足: 令 $y_i = \operatorname{LCM}(x_1, \dots, x_i)$,$\forall 1\le i<N, y_i<y_{i+1}$(即 $y_i$ 单调升)。

加入题单

上一题 下一题 算法标签: