专栏文章

题解：P10426 [蓝桥杯 2024 省 B] 宝石组合

AAuCodingFrogHoward
P10426题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqewmou
此快照首次捕获于
2025/12/04 03:40
3 个月前
此快照最后确认于
2025/12/04 03:40
3 个月前
查看原文
注：本文提到的数均为正整数！！！

证

对于任意 HaH_a，HbH_b，HcH_c，可以设Ha=w×xH_a=w \times x ，Hb=w×yH_b=w \times y ，Hc=w×zH_c=w \times z 。
正确性易证。
∴\therefore lcm⁡(Ha,Hb,Hc)=w×x×y×z\operatorname{lcm}(H_a,H_b,H_c)=w \times x \times y \times z，lcm⁡(Ha,Hb)=w×x×y\operatorname{lcm}(H_a,H_b)= w \times x \times y，lcm⁡(Ha,Hc)=w×x×z\operatorname{lcm}(H_a,H_c)= w \times x \times z，lcm⁡(Hb,Hc)=w×y×z\operatorname{lcm}(H_b,H_c)= w \times y \times z。
代上七式入原式，得：S=w4×x2×y2×z2w3×x2×y2×z2S=\frac{w^4 \times x^2 \times y^2 \times z^2 }{w^3 \times x^2 \times y^2 \times z^2} =w=w
显然，gcd⁡(Ha,Hb,Hc)=w\gcd(H_a,H_b,H_c)=w ， 故：S=wS=w。
问题转化为：求出最大的 ww，最小的 a,b,ca,b,c，使得gcd⁡(a,b,c)=w\gcd(a,b,c)=w。
依题意 % 你枚举云云。细节见注释。

石马：

CPP
#include<bits/stdc++.h>
using namespace std;
int a[300005],zc[100005],zx[100005],cx[100005],sx[100005];
int main()
{
	int n;
	cin>>n;
	memset(zx,0x7f,sizeof(zx));//赋极值，保稳定。 
	memset(cx,0x7f,sizeof(cx));
	memset(sx,0x7f,sizeof(sx));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);//π一遍序 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j*j<=a[i];j++)
		{
			if(a[i]%j==0)
			{
				zc[j]++;
				if(j!=a[i]/j)
				{
					zc[a[i]/j]++;//判平方 
				}
			}
		}
	}
	int xk;
	for(int i=100005;i>=1;i--)//倒序枚举 
	{
		if(zc[i]>=3)//最大找到就退 
		{
			xk=i;
			break;
		}
	}
	for(int i=1,j=1;i<=n,j<=3;i++)//顺序枚举 
	{
		if(a[i]%xk==0)
		{
			j++;
			cout<<a[i]<<" ";
		}
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...