题目描述

宝石组合（蓝桥）

题眼

最大公约和最小公数的关系；
两个数是我们常用最大公约去求最小公倍，公式
$$ ab最小公倍数=\frac{a*b}{ab最大公约数} $$
（原因：可以使用除留余数法很方便的求解最大公因数）
如果熟悉该公式那么看到如题算式应该会“菊花一紧”，只需简单证明即可知道题目中的算式其实是三个数的最大公约数。（证明略，y总本题视频里讲的方法很容易理解，而且更推荐使用y总的方法，y总的方法更像是一种“通用方法”，即便是4个数、5个数也能很方便的推导出来）
问题转变为了：求N个数中（可重），任选三个数的最大公约数所构成集合的最大值。

样例

#include <iostream>

using namespace std;
const int N = 100000;
int count[N+1];


int main()
{
    int n=0,x;
    cin>>n;
    for (int i = 0; i < n; i ++ )
    {
        cin>>x;
        count[x]++;
    }
    for (int i=N;i>0;i--)
    {
        int count_beishu=0;
        for (int j=i;j<=N;j+=i) 
        {
            count_beishu+=count[j];
            if(count_beishu>=3) break;
        }
        if(count_beishu>=3)
        {
            int c=0;
            for (int j=i;j<=N && c<3 ;j+=i)
                for (int k = 0; k < count[j] && c<3; k++,c++ ) cout<< j<< ' ';
            break;

        }

    }
}