Codeforces Round #552 (Div. 3)G. Minimum Possible LCM

题意：给出n个数字，找出$(i,j)$使得$lcm(a_i,a_j)$最小

做法：假设现在有因子$p$，这个序列中能整除p的有五个数$a_1,a_2,a_3,a_4,a_5$（从小到大排），从小到大枚举p的过程中有三种情况: （一）:$gcd(a_1,a_2)=kp>p$，说明在因子$kp$的情况讨论时会包含这种情况，就不用考虑了 （二）:$gcd(a_1,a_2)=p$,此时$lcm(a_1,a_2)=a_1\ast a_2/p$， 1:如果$gcd(a_i,a_j)=p且(i,j)!=(1,2)$，$a_i\ast a_j/p>=a_1\ast a_2/p$，故后面的组合都不用考虑 2.如果$gcd(a_i,a_j)=kp>p$，说明在因子$kp$里面会包含这种情况，就不用考虑了 （三）:$a_1=a_2$，此时$lcm(a_1,a_2)=a_1$显然当前这个子情况中最优的

综上所述，在排除了所有相同数字的影响下，只要暴力枚举[1,maxn]所有p，如果有$n>=2$个数可以整除p，记录下前两个的lcm,和pos1,pos2，不断取最小的lcm即可

复杂度：$O(2\ast 10^7\ast log(10^7))$

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<queue> #include<map> #define ll long long #define pb push_back #define rep(x,a,b) for (int x=a;x<=b;x++) #define repp(x,a,b) for (int x=a;x<b;x++) #define W(x) printf("%d\n",x) #define WW(x) printf("%lld\n",x) #define pi 3.14159265358979323846 #define mem(a,x) memset(a,x,sizeof a) #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r using namespace std; const int maxn=1e7+7; const int INF=1e9; const ll INFF=1e18; int a[maxn],n,val,x,id1,id2; int pos[maxn]; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} int main() { scanf("%d",&n); ll res=INFF; rep(i,1,n) { scanf("%d",&x); a[x]++; if (a[x]>1&&x<res)//如果出现相同的数字 //就把他们的情况取最优解 { res=x; id1=pos[x]; id2=i; } pos[x]=i; } for (ll i=1;i<maxn;i++) { val=0; bool mark=true; for (ll j=i;j<maxn;j+=i) { if (!a[j])continue; else if (a[j]!=0&&mark)//第一个整除i的数 { val=j; mark=false; } else//第二个整除i的数 { ll g=gcd(j/i,val/i); if (g==1) { ll lcm=j/i*val; //这么写可以防止爆范围 if (lcm<res) { res=lcm; id1=pos[val]; id2=pos[j]; } } break; //之前已经解释过，取前两个数字即可 } } } cout<<min(id1,id2)<<" "<<max(id1,id2)<<endl; return 0; }