这道题要求的式子是$gcd({\mathrm{lcm}(a_i,a_j)|1 \leq i <j\leq n})$

很明显可以发现的是:如果在$a_i$中,有大于等于两个数都不是$x$的倍数,那么答案中可定不会出现$x$的倍数。

这十分容易说明,我们对这两个不是$x$的倍数执行$lcm$操作,可以发现结果并没有$x$的倍数。因此,执行$gcd$操作后也不可能出现$x$的倍数。

如果只有一个数不是(或者这些数都是)$x$的倍数的话,无论你怎么两两配对进行$lcm$操作,结果都包含$x$的倍数。因此只要执行$ans*x$就行了。

最后输出$ans$就是答案。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
long long n,s[100010],maxs,ans=1,fi;
bool t[200010];
int main() {
memset(t,1,sizeof(t));
scanf("%I64d",&n);
for(int i=1;i<=n;i++) {
scanf("%I64d",&s[i]);
maxs=max(maxs,s[i]);
}
t[1]=0;
for(int i=2;i<=maxs;i++) //使用埃筛判断素数
for(int j=i+i;j<=maxs;j+=i)
t[j]=0;
for(int i=2;i<=maxs;i++) {
if(!t[i]) continue; //对于每个素数进行判断
bool unfailed=true;
while(unfailed) { //如果发现全部都是x的倍数/只有一个数不是x的倍数,那么就继续查。
fi=0;
for(int j=1;j<=n;j++) {
if(s[j]%i!=0) {
if(fi==0) fi=j;
else {
unfailed=false;
break;
}
}
}
if(!unfailed) break;
for(int j=1;j<=n;j++)
if(j!=fi) s[j]/=i;
ans=(long long)ans*i;//是$x$的倍数,乘起来
}

}
printf("%I64d\n",ans);
return 0;
}

很显然的是,这样写法并不会超时,如果不知道原因,可以在评论区留言或者私信我。