div3G.Teams

发表于 | 分类于


Codeforces Round #552 (Div. 3) G. Two Teams

题意

找到俩个数使他俩的LCM最小,输出这俩个数的下标。

思路

每次枚举每个数的因子,然后求lcm,将最小的LCM的俩个下标存起来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
int a[maxn];
int v[maxn];
int main(){
    int n;
    cin>>n;
    int maxx=0;
    int ans0=0x3f3f3f3f,ans1=0x3f3f3f3f;
    long long  ma=1e16;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxx=max(maxx,a[i]);
        if(v[a[i]]){
            long long temp=a[i];
            if(ma>temp){
                ma=temp;
                ans0=v[a[i]];
                ans1=i;
            }
        }
        v[a[i]]=i;
    }
    for(int i=1;i<=maxx;i++){
        int ans00=-1,ans11=-1;
        for(int j=i;j<=maxx;j+=i){
            if(v[j]){
                if(ans00==-1)  ans00=j;
                else ans11=j;
            }
            if(ans11!=-1&&ans00!=-1)  break;
        }
        if(ans11!=-1){
            long long temp=1ll*ans11*ans00/i;
            if(ma>temp){
                ma=temp;
                ans0=v[ans00];
                ans1=v[ans11];
            }
        }
    }
    if(ans0>ans1) swap(ans0,ans1);
    printf("%d %d\n",ans0,ans1);
}