CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
=====Orac and LCM=====

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

=====推荐理由？=====

思维题，挺思维的，嗯。

=====题意=====

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

=====题解=====

将答案 ans 质因数分解，有 $ans =$ p<sub>1</sub><sup>k1</sup>p<sub>2</sub><sup>k2</sup>...p<sub>m</sub><sup>km</sup>

对于每个 p<sub>i</sub>，一定在序列 s 中出现至少 $n - 1$ 次，每次出现由小到大可能为 p<sub>i</sub><sup>c1</sup>， p<sub>i</sub><sup>c2</sup>， ...p<sub>i</sub><sup>cki</sup>

GCD(LCM(p<sub>i</sub><sup>c1</sup>， p<sub>i</sub><sup>c2</sup>， ...p<sub>i</sub><sup>cki</sup>))一定为第二小的c2

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

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

------

=====AC代码=====

<code c++>
#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);
}
</code>
CVBB ACM Team

用户工具

站点工具

页面工具
