Codeforces B. Minimum Possible LCM（贪心数论）

题目描述：

B. Minimum Possible LCM

time limit per test

4 seconds

memory limit per test

1024 megabytes

input

standard input

output

standard output

You are given an array aconsisting of integers a1,a2,…,a**n

Your problem is to find such pair of indices i,j that lcm(\(a_i\),\(a_j\))is minimum possible.

lcm(x,y) is the least common multiple of and x and y(minimum positive number such that both x and y are divisors of this number).

Input

The first line of the input contains one integer n — the number of elements in a

The second line of the input contains n integers a1,a2,…,an (1≤ai≤107), where ai is the i-th element of a.is the i.

Output

Print two integers i and (1≤i<j≤n is minimum among all valid pairs i,j

思路：

题目是要求一组数中两个数的最小公倍数的最小值。刚开始一个直白的想法就是枚举，把每两个数的gcd求出来，根据gcd求每两个数的lcm。这种做法的时间复杂度为O(\(n^2\log_2 n\))，在看看题目的数据范围，显然不太科学，限时4秒，\(10^{12}log_210^{6}\),会远远超时。怎么办？

我们来想一想，一般lcm问题与gcd问题是挂钩的。怎么样来求，由于数据的范围给定了，考虑枚举数的因子，从1开始到\(10^7\)，在数列中找到一因子为最大公约数的两个最小数，就是答案。为什么？

假设现在枚举到了公因子d，数列中是d的倍数的有\(x_1\)<\(x_2\)<\(x_3\)<...<\(x_n\)，如果d是\(x_1\),\(x_2\)的gcd，那么也就满足条件，x1,x2的最小公倍数肯定最小（在d为因子时）。如果d不是x1,x2的gcd，那也不是后面数的gcd，那么最大公倍数就不会最小。

由于d是从小到大枚举的，如果在d时满足条件，肯定为局部最优解。如果都不满足d为gcd，d++，继续枚举直到满足。由于算法一定会终止，算法的正确性就有了保障。算法复杂度是O(\(n\log_2 n\))

需要注意的是当元素有重复的情况，那么这种元素的最小公倍数就是本身，而且只可能是最小重复元素的时候，因为如果比它大的重复元素的lcm一定大于它，不会是全局最小lcm，单独在输入的时候不断覆盖，留下最小的一种即可。

注意LLONG_MAX和LONG_MAX是不一样的，我一开始错了，原来因为是数不够大。

代码：

#include <iostream>

#include <climits>

#define INF LLONG_MAX

#define max_n 10000007

using namespace std;

long long a[max_n];

int n;

int pos[max_n];

long long ans = 0;

long long minm = INF;

int x = 0;

int y = 0;

long long gcd(long long a,long long b)

{

    return (b==0)?a:gcd(b,a%b);

}

int main()

{

    cin >> n;

    for(int i = 1;i<=n;i++)

    {

        int v;

        cin >> v;

        a[v]++;

        if(a[v]>1&&v<minm)

        {

            minm = v;

            x = pos[v];

            y = i;

        }

        pos[v] = i;

    }

    for(int i = 1;i<max_n;i++)

    {

        long long v = 0;

        for(int j = i;j<max_n;j+=i)

        {

            if(a[j]==0)

            {

                continue;

            }

            if(v==0)

            {

                v = j;

            }

            else

            {

                long long g = gcd(v/i,j/i);

                if(g==1)

                {

                    ans = (long long)j/i*v;

                    if(ans<minm)

                    {

                        //cout << "v " << v << " j " << j << endl;

                        minm = ans;

                        x = pos[v];

                        y = pos[j];

                    }

                }

                break;

            }

        }

    }

    if(x>y) swap(x,y);

    cout << x <<  " " << y << endl;

    return 0;

}

参考文章：

KobeDuu，Minimum Possible LCM【枚举】，https://blog.csdn.net/qq_41157137/article/details/89353527

巴特西

Codeforces B. Minimum Possible LCM（贪心数论）

题目描述：

思路：

代码：

参考文章：

最新文章

热门文章