题目大意
给定集合\(\{a_1,a_2,...,a_n\}\),求\(gcd(\{lcm(\{a_i,a_j\})|i<j\})\)
$2 n 1e5 $ , \(1 \leq a_i \leq 2e5\)
思路
考虑唯一分解定理:
\(a = \prod^{n}_{1}p_i^{k_i}\)
\(b = \prod^{n}_{1}p_i^{g_i}\)
对于 \(gcd\) 和 \(lcm\) ,我们有:
\(gcd(a,b) = \prod^{n}_{1}p_i^{min(k_i,g_i)}\)
\(lcm(a,b) = \prod^{n}_{1}p_i^{max(k_i,g_i)}\)
观察易得,对于答案中的每个质因子\(p_i\),它的指数\(k_i\)为\(\{a_1,...,a_n\}\)中 \(p_i\) 第二小 的指数\(k\)
我们预处理出\(i\)的所有质因数\(p[i]\),将\(a_i\)分解,用\(d[i][j]\)表示\(a_j\)的质因子\(i\)的指数,排序后扫一遍\(d[i]\)即可得到答案
具体来说 \[
ans *= \left\{
\begin{array}{lcl}
i^{d[i][0]}&& {d[i].size() == n-1} \\
i^{d[i][1]} && {d[i].size() \geq n-1 }\\
1 && otherwise
\end{array}
\right.
\]
代码
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+10;
int raw[maxn];
int vis[maxn];
ll Pow(int x,int d){
ll tans = 1;
if(d == 0)return 1;
ll a = Pow(x,d/2);
tans = a*a;
if(d%2)tans = tans*x;
return tans;
}
bool n_prime[maxn];
vector<int>p[maxn],d[maxn];
void prime(){
for(int i = 2;i <maxn;i++){
if(!n_prime[i]){
p[i].push_back(i);
for(int j = i*2;j < maxn;j += i){
n_prime[j] = 1;
p[j].push_back(i);
}
}
}
n_prime[1] = 1;
}
int main(){
prime();
int n;
cin >> n;
for(int i = 1;i <= n;i++)cin >> raw[i];
for(int i = 1;i <= n;i++){
int u = raw[i];
for(int x:p[u]){
int yay = 0;
while(u%x == 0){
yay++;
u /= x;
}
d[x].push_back(yay);
}
}
ll ans = 1;
for(int i = 2;i < maxn;i++){
sort(d[i].begin(),d[i].end());
if(d[i].size() == n-1){
ans *= Pow(i,d[i][0]);
}
else if(d[i].size() > n-1)ans *= Pow(i,d[i][1]);
}
cout << ans;
return 0;
}
|