Orac and LCM（GCD/LCM/质因子分解/推导证明）Codeforces Round #641 (Div. 2) C题

题目大意

       给$n(n \le 100000)$n(n≤100000)个数$a_i(a_i \le 200000)$ai​(ai​≤200000)，求$gcd(\{lcm(\{a_i,a_j\})|i<j\})$gcd({lcm({ai​,aj​})∣i<j}).

分析过程

       考虑每个数的素因子分解，对于$(a_i,a_j)$(ai​,aj​)的所有组合，$lcm(a_i,a_j)$lcm(ai​,aj​)对应的素因子$p^k$pk总满足$k=max(k_i,k_j)$k=max(ki​,kj​)，即取二者最大的那一个，而对于$gcd$gcd来说则是取$min$min。于是，对于结果$ans$ans来说，一定有一个唯一的素数分解，其中每一个素数$p^k$pk的$k$k等于所有$lcm(a_i,a_j)$lcm(ai​,aj​)组合中$p$p的最小值，而对于所有$lcm(a_i,a_j)$lcm(ai​,aj​)来说，能够得到的最小值是所有$a_i$ai​的$p^k$pk的次小值$k$k，因为最小的那个$k$k肯定会由于$lcm$lcm的$max$max特性被掩盖掉，而当最小的$k$k和次小的$k$k对应的$a_i$ai​在一起求$lcm$lcm时，次小的那个$k$k对应的$a_i$ai​会被保留下来。
       所以，这道题先用类似于埃拉斯托特尼筛选法的方式预处理标记一遍$a_i$ai​的最小素因子，然后对于每个$a_i$ai​进行素因子分解，然后维护对应素因子的最小值和次小值即可。

Another Solution

       还有一种做法，利用公式$gcd( lcm(a1 , a2) , lcm(a1 , a3) ... lcm(a1 , an) ) =lcm (a1 , gcd (a2 , a3 , ... an) )$gcd(lcm(a1,a2),lcm(a1,a3)...lcm(a1,an))=lcm(a1,gcd(a2,a3,...an))
这样只需要求前缀和后缀$gcd$gcd就行了。
关于这个公式的证明留个坑，等之后来填~！

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
const int N = 200000;
ll flag[N+5], a[maxn], cnt[N+5][3], n;
void preTreat(){
	int i, j;
	for(i=2;i<=N;++i){ //预处理标记每个数能够被整除的最小素因子 
		if(flag[i]) continue;
		for(j=i;j<=N;j+=i){
			if(!flag[j]) flag[j] = i;
		}
	}
	for(i=1;i<=N;++i) cnt[i][0] = cnt[i][1] = N;
}
void solve(){
	int i;
	ll ans = 1;
	for(i=1;i<=n;++i){
		while(a[i] > 1){
			ll c = 0, temp = a[i]; 
			while(a[i] % flag[temp] == 0){
				a[i] /= flag[temp];
				++c;	
			}
			if(c < cnt[flag[temp]][0]) swap(cnt[flag[temp]][0], c);
			if(c < cnt[flag[temp]][1]) swap(cnt[flag[temp]][1], c);
			++cnt[flag[temp]][2]; //记录此因子存在于多少个树中 
		} 
	}
	for(i=2;i<=N;++i){
		if(cnt[i][2] < n - 1) continue;
		ll j = cnt[i][1];
		if(cnt[i][2] == n - 1) j = cnt[i][0];
		while(j--) ans *= i; 
	}
	cout<<ans;
} 
int main(){
	int i;
	ios::sync_with_stdio(false);
	cin>>n;
	for(i=1;i<=n;++i) cin>>a[i];
	preTreat();
	solve();
	return 0;
}