time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array a1,a2,…,ana1,a2,…,an where all aiai are integers and greater than 00.
In one operation, you can choose two different indices ii and jj (1≤i,j≤n1≤i,j≤n). If gcd(ai,aj)gcd(ai,aj) is equal to the minimum element of the whole array aa, you can swap aiai and ajaj. gcd(x,y)gcd(x,y) denotes the greatest common divisor (GCD) of integers xx and yy.
Now you'd like to make aa non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.
An array aa is non-decreasing if and only if a1≤a2≤…≤ana1≤a2≤…≤an.
Input
The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The first line of each test case contains one integer nn (1≤n≤1051≤n≤105) — the length of array aa.
The second line of each test case contains nn positive integers a1,a2,…ana1,a2,…an (1≤ai≤1091≤ai≤109) — the array itself.
It is guaranteed that the sum of nn over all test cases doesn't exceed 105105.
Output
For each test case, output "YES" if it is possible to make the array aa non-decreasing using the described operation, or "NO" if it is impossible to do so.
Example
input
Copy
4 1 8 6 4 3 6 6 2 9 4 4 5 6 7 5 7 5 2 2 4output
Copy
YES YES YES NONote
In the first and third sample, the array is already non-decreasing.
In the second sample, we can swap a1a1 and a3a3 first, and swap a1a1 and a5a5 second to make the array non-decreasing.
In the forth sample, we cannot the array non-decreasing using the operation.
解题说明：此题是一道模拟题，先求出排好序的数组，然后再判断需要交换的数字是否能够整除排序后的数组的最小值即可。如果能够整除，那gcd一定不会小于该数，否则就无法进行交换。
#include<bits/stdc++.h> #include<iostream> #include<algorithm> using namespace std; int b[100009]; int a[100009]; int main() { int t; cin >> t; while (t--) { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i]; } sort(b + 1, b + 1 + n); int f = 0; for (int i = 1; i <= n; i++) { if (a[i] != b[i]) { if (a[i] % b[1] != 0) { f = 1; break; } } } if (f == 1) { cout << "NO" << endl; } else { cout << "YES" << endl; } } return 0; }
