自动搬运

查看原文

来自洛谷，原作者为

	suzy0921 弱爆了的菜鸡很困

搬运于2025-08-24 22:57:52，当前版本为作者最后更新于2024-08-14 19:23:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目分析

看到那么大长串的柿子不要慌

我们把式子 $H _ {a}$ 看作圈 $a$ ,把式子 $H _ {b}$ 看作圈 $b$ ,把式子 $H _ {c}$ 看作圈 $c$

$$\begin{aligned} S &= H _ {a} H _ {b} H _ {c} \cdot \frac{\operatorname{LCM}(H _ {a}, H _ {b}, H _ {c})}{\operatorname{LCM}(H _ {a}, H _ {b}) \cdot\operatorname{LCM}(H _ {a}, H _ {c}) \operatorname{LCM}(H _ {b}, H _ {c})}\\ &= (d \times h \times j \times g) \times (g \times j \times e \times i) \times (j \times i \times h \times f) \times\frac{(d \times e \times f \times g \times h \times i \times j)}{(d \times g \times h \times j \times i \times f) \times (d \times g \times h \times j \times e \times i) \times (h \times j \times i \times f \times g \times e)} \end{aligned}\\ $$

化简完之后我们得到了

$$S=j\\$$

$j$ 指的是 $\gcd(H _ {a},H _ {b},H _ {c})$，所以

$$S=\gcd(H _ {a},H _ {b},H _ {c})$$

做题思路

1.找一个 $cnt[i]$ 用于记录从 $H _ {1}，H _ {2}$ 一直到 $H _ {n}$ 中能被 $i$ 整除的个数。
2.找到最大的 $i$ 使得 $cnt[i] \ge 3$ 记为 $x$
3.从小到大排序 $H$ 数组。
4.从 $1$ 到 $n$ 遍历，判断 $H _ {i}\mid x$ ，输出前 3 个满足要求的数。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],cnt[N];
int main()
{
	int n,x,c=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
		for(int j=1;j*j<=h[i];j++) {
			if(h[i]%j==0){
				cnt[j]++;
				if(j*j!=h[i]) cnt[h[i]/j]++; 
			}
		}
	}
	for(int i=N-5;i>=1;i--){
		if(cnt[i]>=3){
			x=i;
			break;
		}
	}
	sort(h+1,h+n+1);
	for(int i=1;i<=n;i++){
		if(h[i]%x==0){
			cout<<h[i]<<" ";
			c++;
		}
		if(c==3) return 0;
	}
	return 0;
}

完结撒花 点个赞趴