题解

思路

答案为 Yes 当且仅当 $N$ 至少含两个不同质因子。

做法

若 $N=p^e$ 是质数幂，因为至少要选两个正整数，所以每个 $A_i<N$；同时最小公倍数为 $N$ 又要求每个 $A_i$ 都整除 $N$，于是所有 $A_i$ 至多整除 $p^{e-1}$，最小公倍数不可能达到 $N$。反之，若 $N$ 有不同质因子 $p,q$，令 $k=N-N/p-N/q$；由 $p\ge2,q\ge3$ 得 $k>0$，取 $k$ 个 $1$、一个 $N/p$ 和一个 $N/q$，总和为 $N$，最小公倍数也恰为 $N$。因此只需试除并统计不同质因子的个数，达到两个即可提前结束。

复杂度

每组数据的时间复杂度为 $O(\sqrt N)$，额外空间复杂度为 $O(1)$。