C++(g++ 7.5.0) 解法, 执行用时: 231ms, 内存消耗: 1408K, 提交时间: 2022-11-08 12:42:07

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+9;
int p[N],hp,lpf[N],cnt[N],idx[N];
bool vis[N];
void sieve(int n){
	for(int i=2;i<=n;++i){
		if(!vis[i])p[++hp]=i,lpf[i]=i,idx[i]=hp;
		for(int j=1,x;j<=hp&&(x=i*p[j])<=n;++j){
			vis[x]=1;lpf[x]=p[j];
			if(i%p[j]==0)break;
		}
	}
}
int main(){
	sieve(100000);
	int n;scanf("%d",&n);
	for(int i=1;i<=n;++i){
		int x;scanf("%d",&x);
		while(x>1){
			int t=lpf[x],c=0;
			while(x%t==0)x/=t,++c;
			cnt[idx[t]]=max(cnt[idx[t]],c);
		}
	}
	long long ans=1;
	for(int i=1;i<=hp;++i){
		for(int j=1;j<=cnt[i];++j){
			ans=ans*p[i]%mod;
		}
	}
	printf("%lld\n",ans);
} 

C++11(clang++ 3.9) 解法, 执行用时: 912ms, 内存消耗: 6392K, 提交时间: 2020-07-10 11:20:21

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int ans[100005];
int maxn;
const int mod=1e9+9;
void solve(int x)
{
	for(int i=2;i<=sqrt(x);i++)
	{
		int temp=0;
		if(x%i==0) maxn=max(maxn,i);
		while(x%i==0)
		{
			x/=i;
			temp++;
		}
		ans[i]=max(ans[i],temp);
	}
	if(x!=0)
	{
		maxn=max(maxn,x);
		ans[x]=max(ans[x],1);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		solve(x);
	}
	long long res=1;
	for(int i=1;i<=maxn;i++)
	{
		int temp=pow(i,ans[i]);
		res=((temp%mod)*(res%mod))%mod;
	}
	printf("%lld",res);
	return 0;
 } 

C++14(g++5.4) 解法, 执行用时: 631ms, 内存消耗: 4344K, 提交时间: 2020-08-05 21:58:13

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9;
const int N=1e6+1;
typedef long long LL;
int f[N],n,x;
void get(int x)
{
    for(int j=2;j<=sqrt(x);j++)
    {
        int temp=1;
        while(x%j==0)
        {
            x/=j;
            temp*=j;
        }
        f[j]=max(f[j],temp);
    }
    if(x>0) f[x]=max(f[x],x);
}
int main()
{
    ios::sync_with_stdio(false);
    LL sum=1;
    cin>>n;
    for(int i=1;i<=N-1;i++) f[i]=1;
    while(n--)
    {
        cin>>x;
        get(x);
    }
    for(int i=1;i<=N-1;i++)
        sum=sum*f[i]%mod;
    cout<<sum;
}