[CF1154G] Minimum Possible LCM

[CF1154G] Minimum Possible LCM

Description

给定一个长度为 (n) 的序列 (a (a_i le 10^7))，找出两个数，最小化他们的最小公倍数

Solution

用桶维护，然后枚举 GCD=i，然后枚举能被 i 整除的数中选最小的俩去更新答案

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e7 + 5;

int a[N], n, s[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a[x]++;
        s[i] = x;
    }
    int ans = 1e18, ansx = 0, ansy = 0;
    for (int i = 1; i <= 1e7; i++)
    {
        vector<int> vec;
        for (int j = i; j <= 1e7; j += i)
        {
            if (a[j] > 0)
                vec.push_back(j);
            if (a[j] > 1)
                vec.push_back(j);
            if (vec.size() > 1)
                break;
        }
        if (vec.size() > 1)
        {
            int tmp = vec[0] * vec[1] / i;
            if (tmp < ans)
            {
                ans = tmp;
                ansx = vec[0];
                ansy = vec[1];
            }
        }
    }
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++)
        if (s[i] == ansx)
        {
            x = i, s[i] = 1e18;
            break;
        }
    for (int i = 1; i <= n; i++)
        if (s[i] == ansy)
        {
            y = i, s[i] = 1e18;
            break;
        }
    if (x > y)
        swap(x, y);
    cout << x << " " << y << endl;
}