欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

清北学堂day3

程序员文章站 2022-05-31 19:13:39
T1 gcdlcm 用cnt[i]记录i出现了多少次,枚举约数d,检查cnt[j*d] (j*d<=maxn),用f,g记录最大值和次大值; 若cnt[j*d]>=2,则f,g都更新为j*d; 若cnt[j*d]==1则g=f,f=j*d; 若f>0,g>0,则答案更新为f*g/d; 注:若f与g相 ......

t1 gcdlcm

 

用cnt[i]记录i出现了多少次,枚举约数d,检查cnt[j*d] (j*d<=maxn),用f,g记录最大值和次大值;

cnt[j*d]>=2,则fg都更新为j*d

cnt[j*d]==1g=f,f=j*d;

f>0,g>0,则答案更新为f*g/d;

注:若fg相同,由于上面的d会枚举到,所以不会影响答案;

code:

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int n=1e6+100;
typedef long long ll;
int cnt[n],a[n],n,maxn,f,g;
ll ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++,maxn=max(maxn,a[i]);
    for(int d=1;d<=maxn;d++){
            f=0,g=0;
        for(int j=1;1ll*j*d<=maxn;j++){
            if(cnt[j*d]>=2){
                f=1ll*j*d;g=1ll*j*d;
            }else if(cnt[j*d]==1){
                g=f;f=1ll*j*d;
            }
        }
        if(f>0&&g>0){
         ans=1ll*f*g/d;
        }
    }
    printf("%lld",ans);
    return 0;
}