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

· · 题解

注：本文提到的数均为正整数！！！

证

对于任意 H_a，H_b，H_c，可以设H_a=w \times x ，H_b=w \times y ，H_c=w \times z 。

正确性易证。

\therefore 代上七式入原式，得：$S=\frac{w^4 \times x^2 \times y^2 \times z^2 }{w^3 \times x^2 \times y^2 \times z^2} =w

显然，\gcd(H_a,H_b,H_c)=w ， 故：S=w。

问题转化为：求出最大的 w，最小的 a,b,c，使得\gcd(a,b,c)=w。

依题意 % 你枚举云云。细节见注释。

石马：

#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]<<" ";
        }
    }
}