【CF1154G】Minimum Possible LCM

题意

给你 \(n\) 个数 \(a_i\) ，求出 \(\text{lcm}\) 最小的一对数。

\(n\le 10^6, a_i\le 10^7\)

题解

直接枚举，找到当前数最小的两个倍数，统计答案即可。

理论时间复杂度为 \(O(a_i\log a_i)\) ，实际运行效率要远高于此。

代码很好写。

#include<cstdio>

const int N=10000005;

int a[N],a2[N],aid[3],mx,n;

long long ans=1ll<<60;

inline int gi()

{

	char c=getchar(); int x=0;

	for(;c<'0'||c>'9';c=getchar());

	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';

	return x;

}

int main()

{

	n=gi();

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

	{

		int x=gi();

		a[x]?a2[x]=i:a[x]=i;

		if(x>mx) mx=x;

	}

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

	{

		int v[3],id[3],tot=0;

		for(int j=i;tot<2&&j<=mx;j+=i)

			if(a[j])

			{

				v[++tot]=j,id[tot]=a[j];

				if(a2[j]&&tot!=2) v[++tot]=j,id[tot]=a2[j];

			}

		if(tot==2&&ans>1ll*v[1]*v[2]/i)

		{

			ans=1ll*v[1]*v[2]/i;

			aid[1]=id[1],aid[2]=id[2];

		}

	}

	if(aid[1]>aid[2]) aid[1]^=aid[2]^=aid[1]^=aid[2];

	printf("%d %d",aid[1],aid[2]);

}

巴特西

【CF1154G】Minimum Possible LCM

题意

题解

最新文章

热门文章