import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while (t > 0) {
int n = s.nextInt();
int[] arr = new int[n];
for (int i = 0; i <= n - 1; i++) {
arr[i] = s.nextInt();
}
if(t!=1) {
if (selectionSort(arr)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}else{
if(selectionSort(arr)){
System.out.print("YES");
}else {
System.out.print("NO");
}
}
t--;
}
}
public static int gcd(int m, int n) {
int i = 0, t, x;
while (m % 2 == 0 & n % 2 == 0) {
m /= 2;
n /= 2;
i++;
}
if (m < n) {
t = m;
m = n;
n = t;
}
while (n != (m - n)) {
x = m - n;
m = (n > x) ? n : x;
n = (n < x) ? n : x;
}
if (i == 0)
return n;
else
return (int) Math.pow(2, i) * n;
}
public static boolean selectionSort(int[] a) {
int N = a.length;
if (N==0){
return true;
}
int minNum = getMin(a);
for (int i = 0; i < N - 1; i++) {
//length = 5 i = 0 1 2 3 4 i= 0 j =1234
int min = i;
for (int j = i + 1; j < N; j++) {
//将a[i]和a[i+1...N-1]中的最小元素交换
if (a[j] < a[min]) {//升序排列
min = j;
}
}
if (min != i) {//一下是排序过程 a[min]跟a[i]进行交换
if (gcd(a[min], a[i]) != minNum) {
return false;
} else {//要不然就一直排序下去
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
return true;
}
public static int getMin (int[] arr){
int minNum = arr[0];
for (int i = 1; i < arr.length; i++) {
if (minNum > arr[i]) {
minNum = arr[i];
}
}
return minNum;
}
}
说明只有测试样例对了,真正测评的时候他的数据可能是边界的测试
你没注意的点可能有:
1、小猪的身高小于1e9,你用int数组是存不下的。
2、测试过程中,是先输入多组数据,后输出所有的结果。
应该用二维数组存多组数据,结果存一维数组中,最后输出结果。
问题1可以先改造一下,用long类型存,进行验证。
问题2在问题1修改后,还不能通过再修改验证。
真抱歉,题目我都看不懂。