CVBB ACM Team

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

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

啊好，还没写呢

AC代码

#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);
}