/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
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