这道题就是一道纯暴力。。。我居然 WA 了

前置知识：$\gcd(a,b)>1$ 表示两个数不互质。

首先，分析一下数据范围，$n \leq 2000$ 的情况下，两层循环枚举 $i$ 和 $j$，$2000$ 的平方可以过。

现在，再来看看怎么将数组重排才是最优解。思考一下：什么情况下 $\gcd(a_i,a_j)=1$ ，但$\gcd(a_i,a_j\times2)$ 却会大于 $1$ 呢？现在假设 $a_i$ 是偶数，$a_j$ 是奇数，是不是正好满足上面的性质？所以 $a_i$ 是偶数的情况下，无论 $a_j$ 变成什么，乘二后都会变成偶数，两个偶数的最大公因数肯定会大于 $1$，再来分析一下样例：

4
3 6 5 3

如果把奇数和偶数分开，把偶数放在前面，奇数放在后面，样例就变成了6 5 3 3，然后再两层 for 循环枚举 $i$ 和 $j$，最后符合条件的就剩下了 $6,2\times 5$、$6,2\times 3$、$6,2\times 3$、$3,2\times 3$，正好是 $4$ 对。

最后，总结一下此题思路：将数组中的所有偶数放在前面，奇数放后面，然后循环暴力枚举符合条件的数量就可以 AC。

AC 代码很简单，学过入门的都会，只提供判断 gcd 函数的代码（辗转相除法）

int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}