Codeforces B. Minimum Possible LCM(贪心数论)
题目描述:
B. Minimum Possible LCM
time limit per test
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。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