CVBB ACM Team

题目链接https://codeforc.es/contest/1350/problem/C

思维题，挺思维的，嗯。

给定长为 n ($2≤n≤10^5$)的正整数序列{s₁,s₂,…,s_n}，求由任意两元素 LCM（最小公倍数）组成新序列{a₁,a₂,…,a_n}(1$≤$a_i$≤2*10^5$)的 GCD（最大公约数），即LCM(GCD(s_i,s_j))($i ≤j$)

将答案 ans 质因数分解，有 $ans =$ p₁^k1p₂^k2…p_m^km

对于每个 p_i，一定在序列 s 中出现至少 $n - 1$ 次，每次出现由小到大可能为 p_i^c1， p_i^c2， …p_i^cki

GCD(LCM(p_i^c1， p_i^c2， …p_i^cki))一定为第二小的c2

所以可以对序列 s 每个数的每个质因子统计次数，将大于 $n-1$ 次的因子幂次方排序，取第二小累乘即可

注意用vector，不要处处longlong，否则会MLE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const ll mod = 998244353;
const int maxn = 2e5 + 5; 
 
vector<int> ep[maxn];
 
ll qpow(int k, ll b){
	ll res = 1;
	while(b){
		if(b & 1) res *= k;
		k *= k;
		b >>= 1;
	}
	return res;
}
 
int main(){
	int n;	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		int t;	scanf("%d", &t);
		for(int i = 2; i * i <= t; ++i){
			ll cnt = 0;
			while(t % i == 0){
				t /= i;
				++cnt;
			}
			ep[i].push_back(cnt);
		}
		if(t != 1) ep[t].push_back(1);
	}
 
	ll ans = 1;
	for(int i = 1; i <= maxn; ++i){
		if(ep[i].size() >= n - 1){
			sort(ep[i].begin(), ep[i].end());
			if(ep[i].size() == n) ans *= qpow(i, ep[i][1]); 
			else ans *= qpow(i, ep[i][0]); 
		}
	}
	printf("%lld", ans);
}