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; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/89838.html
標籤：C++
上一篇：C++貪心演算法實作活動安排問題
下一篇：Create an op on tensorflow; 在tensorflow 1.7/2.0 中創建一個 Op操作