C. Orac and LCM
链接：https://codeforces.ml/contest/1350/problem/C
For the multiset of positive integers s={s1,s2,…,sk}s={s1,s2,…,sk}, define the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of ss as follow:
- gcd(s)gcd(s) is the maximum positive integer xx, such that all integers in ss are divisible on xx.
- lcm(s)lcm(s) is the minimum positive integer xx, that divisible on all integers from ss.
For example, gcd({8,12})=4,gcd({12,18,6})=6gcd({8,12})=4,gcd({12,18,6})=6 and lcm({4,6})=12lcm({4,6})=12. Note that for any positive integer xx, gcd({x})=lcm({x})=xgcd({x})=lcm({x})=x.
Orac has a sequence aa with length nn. He come up with the multiset t={lcm({ai,aj}) | i<j}t={lcm({ai,aj}) | i<j}, and asked you to find the value of gcd(t)gcd(t) for him. In other words, you need to calculate the GCD of LCMs of all pairs of elements in the given sequence.
Input
The first line contains one integer n (2≤n≤100000)n (2≤n≤100000).
The second line contains nn integers, a1,a2,…,ana1,a2,…,an (1≤ai≤2000001≤ai≤200000).
Output
Print one integer: gcd({lcm({ai,aj}) | i<j})gcd({lcm({ai,aj}) | i<j}).
Examples
input
Copy
2 1 1
output
Copy
1
input
Copy
4 10 24 40 80
output
Copy
40
input
Copy
10 540 648 810 648 720 540 594 864 972 648
output
Copy
54
Note
For the first example, t={lcm({1,1})}={1}t={lcm({1,1})}={1}, so gcd(t)=1gcd(t)=1.
For the second example, t={120,40,80,120,240,80}t={120,40,80,120,240,80}, and it's not hard to see that gcd(t)=40gcd(t)=40.
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
#define ll long long
#define lb long double
#define INF 0x3f3f3f3f
#define maxn 200010
ll n,k,l,t,x,s;
ll a[200001];
ll dp[100001];
map<ll,ll>m;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
m[a[i]]++;
}
k=1;
for(ll i=2;i<=200000;i++)
{
for(ll j=i+i;j<=200000;j+=i)
{
m[i]+=m[j];
}
if(m[i]>=n-1)
{
k*=i/__gcd(i,k);
}
}
cout<<k;
}
