清北学堂day3

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相同,由于上面的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;
}

 

上一篇:[Codeforces 1265E]Beautiful Mirrors


下一篇:习题:Single-use Stones