AT_arc122_e.[ARC122E] Increasing LCMs

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个长度为 $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$ ，如果存在，请给出一个例子。

输入格式

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

$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
```
输入#2
```
3
2 3 6
```
输出#2
```
No
```

输入#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 \leq N \leq 100$
$2 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}$
输入的所有值均为整数。

样例解释 1

当 $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

无论如何排列 $A$ ，都无法满足条件。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页