CF #552（div3）G 最小lcm

题目链接：http://codeforces.com/contest/1154/problem/G

题意：lcm是最小公倍数，本题就是给你一个数组（可能会重复），要求你判断出那两个数的最小公倍数最小，并输出这两个数的下标

分析：首先想重复，因为重复的话非常好整，最小公倍数就是它自己，所以我们可以先处理一遍，把出现过的重复的数最小的先设为答案（ans）。

另外，记得初始化ans,这里有个坑，记得不要初始化为inf，因为最小公倍数是会爆int的，这点要注意。

然后再开始从1-ans遍历，对于每个数，都不断加倍，来寻找答案,遍历完后输出答案。

注意输出是下标。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;//这个数是1e9数量级的，且可以用memset函数 
const int maxn=1e7+7;
const double pi=acos(-1);
const int mod=1e9+7;
int idx[maxn];//idx[x]存的是数值x的下标 
int main(){
    int n;scanf("%d",&n);
    int t1=0,t2=0,x;ll ans=1e14;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(idx[x]){
            if(ans>x) 
            t1=idx[x],t2=i,ans=x;
        }
        else idx[x]=i;
    }
    for(int i=1;i<=maxn;i++){//因为ans是一直在动态变化的，所以这里终止条件我们设为maxn 
        if(i>=ans) break;
        int s1=0,s2=0;//s1,s2分别记录接下来循环存在的第一个数的值和下标 
        for(int j=i;j<=maxn;j+=i){
            if(!idx[j]) continue;
            if(!s1) s1=j,s2=idx[j]; 
            else{
                if(ans>1ll*j*s1/i){//最小公倍数=两数乘积/最大公因数     这里可能会溢出，记得转化 
                    ans=1ll*j*s1/i;
                    t1=s2,t2=idx[j];
                    break;
                }
            }
        }
    }
    if(t1>t2) swap(t1,t2);
    cout<<t1<<" "<<t2<<endl;
    return 0;
}