给出一个长度为
n
n
n的数组
a
a
a，你可以对这个数组进行如下操作：对于数组
a
a
a中任意的两个元素
a
i
a_i
ai、
a
j
a_j
aj，若
g
c
d
(
a
i
,
a
j
)
=
m
i
n
{
a
1
,
a
2
,
.
.
.
,
a
n
}
gcd(a_i,a_j)=min\{a_1,a_2,...,a_n\}
gcd(ai,aj)=min{a1,a2,...,an}，那么就可以交换数组中的这两个数字。
现在问你是否能够通过一定次的上述操作使得数组
a
a
a变成非递减序列。
思路：
首先，由于
m
i
n
{
a
1
,
a
2
,
.
.
.
,
a
n
}
min\{a_1,a_2,...,a_n\}
min{a1,a2,...,an}是定值，那么对于任何数字
a
i
a_i
ai，只要
a
i
a_i
ai是
a
m
i
n
a_{min}
amin的倍数，都可以构成
g
c
d
(
a
i
,
a
m
i
n
)
=
a
m
i
n
gcd(a_i,a_{min})=a_{min}
gcd(ai,amin)=amin，换句话说只要
a
i
a_i
ai是
a
m
i
n
a_{min}
amin的倍数，
a
i
a_i
ai和
a
m
i
n
a_{min}
amin都是可以随意交换的。反之，如果
a
i
a_i
ai不是
a
m
i
n
a_{min}
amin的倍数，那么数字
a
i
a_i
ai无论如何都不可能被移动，原因在于：既然
a
i
a_i
ai不是
a
m
i
n
a_{min}
amin的倍数，那么对
a
i
a_i
ai进行分解必然不可能得到
a
m
i
n
a_{min}
amin，那么
a
i
a_i
ai与任何其他数字
a
j
a_j
aj的公因数都不可能分解出
a
m
i
n
a_{min}
amin，那么
g
c
d
(
a
i
,
a
j
)
gcd(a_i,a_j)
gcd(ai,aj)也就不可能等于
a
m
i
n
a_{min}
amin了。
其次，将数组
a
a
a进行排序可以得到数组
b
b
b，那么如果
b
[
i
]
≠
a
[
i
]
b[i]\not=a[i]
b[i]=a[i]那必然是通过交换数字得到的，而交换数字就可以通过上面说到的方式进行交换。对所有的
b
[
i
]
≠
a
[
i
]
b[i]\not=a[i]
b[i]=a[i]，若
a
[
i
]
%
a
m
i
n
a[i]\%a_{min}
a[i]%amin都等于
0
0
0，那么就可以通过题目给出的操作的到非递减序列
b
b
b，否则不可以。
对于上面一条不理解的可以这样想，我们把序列中
a
[
i
]
≠
b
[
i
]
a[i]\not=b[i]
a[i]=b[i]的数字
a
[
i
]
a[i]
a[i]以及
a
m
i
n
a_{min}
amin保留下来，然后用
a
m
i
n
a_{min}
amin作为临时变量对剩下的序列进行选择排序，必然可以使得这个序列变成非递减序列，让后再把删除的数字加进去就可以得到数组
b
b
b。删与不删本质上都是一样的，只是为了更好地理解。
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
const int INF = 0x3f3f3f3f;
const int Maxn = 100005;
int a[Maxn], b[Maxn];
void solve() {
int n, minn = INF;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
minn = std::min(minn, a[i]);
}
memcpy(b, a, sizeof a);
std::sort(b, b + n);
bool flag = true;
for (int i = 0; i < n; i++) {
if (a[i] != b[i] && a[i] % minn != 0) {
flag = false;
break;
}
}
printf("%s\n", flag ? "YES" : "NO");
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}