~~因为比赛的时候数据比较水，暴力原本能拿满的，但是后面怕T掉，改了个线性筛的，结果有个地方写错了，导致T了，悲痛啊。~~

分析

首先我们想到了暴力分别求出 \(gcd,lcm\) 和乘积，然后判断是否相等，但是当数列中的数足够大的时候，求 \(gcd\) 的时候会超时，而且乘积就算是 unsigned long long 也存不下（听说好像 int_128 可以存，主要是超时）， ~~但是比赛的时候实在想不出来，倒是可以用来骗分~~。

那么我们再来思考一下，什么时候 \(gcd \times lcm\) 会不等于乘积。

首先，经验告诉我们如果只有两个数的时候，显然 \(gcd \times lcm\) 是等于乘积的。

我们再来思考一下多个数的时候，如果所有数都互相互质，那么他们的最小公倍数就必然是每个数的乘积，最大公因数必然是 \(1\)，这个时候也满足 \(gcd \times lcm\) 等于乘积。

我们再把情况拓展到多个数，但并不是所有数都互相互质的时候，假设有 \(k\) 个数，他们都有相同的质因子 \(p\)，那么最小公倍数必然会等于乘积除以 \(p^{k-1}\)，如果 \(k=n\)，则最大公因数会乘以 \(p\)，因为 \(n>2\)，所以最小公倍数减少的必然比最大公因数增加的多，而如果 \(k<n\)，那么最大公因数甚至不会增加。

所以我们可以得出一个结论，那就是当 \(n>2\) 时，每多出来一个共同质因子，\(gcd\times lcm\) 就会减小，所以只有 \(n=2\) 或者所有数都两两互质的时候， \(gcd\times lcm\) 才会等于乘积之和。

那么，怎么判断所有数都两两互质呢？

我们首先想到统计质因数出现次数，如果出现了一个数，他的某个质因数在之前出现过，那么这个数列必然不满足情况。再特判一下 \(n=2\) 的情况，但是每次质因数分解的时间都比较长，容易超时。

目前能AC的代码

~~因为数据有点水，所以这个能过（以后大概就过不了了）。~~

#include<bits/stdc++.h>//不合乎周礼的代码
using namespace std;
int T,n,gc,a,mul,lc;
map<int,int>m;
bool flag;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n),flag=0,m.clear();
		if(n==2) flag=1;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a);
			if(!flag)
			{
				for(int i=2;i*i<=a;i++)//暴力质因数分解，如果a很大，那么这将消耗很长的时间，容易TLE
				{
					if(a%i==0)
					{
						if(m[i]){flag=1;break;}
						m[i]=1;
						while(a%i==0) a/=i; 
					}
				}
				if(!flag&&a>1)
				{
					if(m[a]) flag=1;
					m[a]=1;
				}
			}
		}
		if(n==2||!flag) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

优化

但是，这个代码在出题人更新数据后多半就会T掉，所以我们还需要进行优化。那么，我们该如何优化呢？

我们很快就能想到，既然是质因数分解，那么我们很自然地想到了线性筛。

对于每个数，我们可以用线性筛进行筛质数，如果筛出来的质数是数列中某个数的因数，那么就可以加入统计。

真·AC代码

#include<bits/stdc++.h>//同样不合乎周礼的代码
using namespace std;
int T,n,a[500005],num[100000005];
bool flag;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n),flag=0,memset(num,0,sizeof(num));//多组数据记得要清零
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		if(n==2){printf("Yes\n");continue;}//先特判特殊情况
		for(int i=1;i<=n;i++)
		{
			for(int j=2;j*j<=a[i];j++)//类似线性筛，最先找到的因子都必然是质因子，而不是质数的因子都会因为他的质因子而提前筛掉
				if(a[i]%j==0)
				{
					if(num[j]){flag=1;break;}//如果记录过则标记
					num[j]++;
					while(a[i]%j==0) a[i]/=j;
				}
			if(flag) break;
			if(a[i]>1)
			{
				if(num[a[i]]){flag=1;break;}
				num[a[i]]++;
			}
		}
		if(flag) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}