自动搬运

查看原文

来自洛谷，原作者为

	Matrix__ CQBZ(hf) 新初二菜鸟同学~~

搬运于2025-08-24 22:57:59，当前版本为作者最后更新于2024-04-20 16:55:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

这个其实很水的思维题，但我赛时却想了 50 分钟。

将数组 $x$ 从小到大排序。

很显然，根据 $\gcd(a,b) \le \min(a,b)$，就可以发现 $x_n$ 和 $x_{n-1}$ 一定不会被删去。那么数组 $x$ 想进行 $x-2$ 此操作就必须将 $x_1 \cdots x_{n-2}$ 都删去。

继续，我们现在想把 $x_1 \cdots x_{n-2}$ 都删去。

那么此时，$x_{n-2}$ 和 $x_{n-3}$ 就是最大的了，最后肯定会剩下他俩，那么他俩想被约去，就必须是 $\gcd(x_n,x_{n-1})$。同理可得：那前面的数想被约掉，就必须得是 $\gcd(x_{n-2},x_{n-3})=\gcd(\gcd(x_n,x_{n-1}),\gcd(x_n,x_{n-1}))=\gcd(x_n,x_{n-1})$。

那么可得：这个数组 $x$ 能进行 $n-2$ 此操作，当且仅当任意一个 $i$（$1 \le i \le n-2$）皆满足 $x_i=\gcd(x_n,x_{n-1})$。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 III;
const db eqs=1e-6;
const int inf=1e9;
void cmax(int &a,int b){a=max(a,b);}
void cmin(int &a,int b){a=min(a,b);}
bool db_eq(db a,db b){return fabs(a-b)<eqs;}

const int MAXN=1000000+5;
int T,n,a[MAXN];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+n+1);
		if(n==2) 
		{
			cout<<"Yes\n";
			continue;
		}
		bool flag=1;
		for(int i=1;i<=n-2;i++)
		{
			if(a[i]!=__gcd(a[n],a[n-1]))
			{
				cout<<"No\n";
				flag=0;
				break;
			}
		}
		if(flag) cout<<"Yes\n";
	}	
	return 0;
}