第十五届蓝桥杯C/C++组:宝石组合题目（从小学奥数到编程题详解）

这道题目真的一看就不好做，如果直接暴力去做百分之90必挂掉，那么这道题目到底应该怎么去做呢？这我们就得从小学奥数开始聊了。（闲话：自从开始蓝桥杯备赛后，每天都在被小学奥数震惊，为什么我小的时候没学过这些，我要重开！重开！！！）

1.小学奥数知识补充

1.1分解质因数

分解质因数对于很多人来说并不陌生，甚至可以说是随手就能解决。就算不会听了名字也一秒就会了就是把一个数字拆成自己的几个是质数因数的乘积。
那么我们可以可以小试一下，方便我们找回初中的记忆。如:
$$12=2^2\ast 3;15=3\ast 5;5=1^{\ast }5$$

1.2解决最小共倍数

很多人也都会分解质因数，但是不知道这个有什么用，到底要因用在哪里，而这道题目我们要用的就是去解决最小公倍数。
那么怎么解决呢？如下图

1.3解决最大公约数的问题

分解质因数法求最大公约数：将每个数分解成质因数的乘积，然后取所有质因数中的最小幂次相乘得到的结果即为最大公约数。例如，求解48和60的最大公约数，分解质因数后可得

$$48=3\ast 2^4，60=5\ast 3\ast 2^2;最终可最大公约数为4\ast 3=12$$

2解题思路

当然小学奥数知识只是一个前置条件，你有了也未必能想到下面的思路，下面开始下面的解题思路

首先我们可以将Ha,Hb,Hc全部拆解质因数（为什么会想到这样，主要还是为了化简这个复杂的式子。）
这里我们把HaHbHc表示成他们所有的质因数的幂的乘积（这里有的幂是0）

然后们再看旁边的式子

LCM其实就是我们三个所有的质因数的里面去取那个幂最大的玩，那么既然我们要依次对所有的质因数去带入这个式子，那么我们的式子就变成了

这样看着就舒服很多，然后我们再进行化简
这里我们把上面三个字母设成X>=Y>=Z

那么这个Z其实就是他们的质因数的最小的那个，那他们所有质因数的最小的幂的乘积其实就是最大公约数也就是我们上面说的

那么这道题目的难度瞬间少了一沓，就是求三个数的最大公约数的最大值。

然后我们还可以利用题目给的下面的值，最大是10^5，来减少时间复杂度（也就是我们最多只要枚举到最大值就行）

3.代码实现

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int m;
        cin>>m;
        a[m]++;//记录m出现了多少次
    }
    for(int i=N-1;i>=1;i--){
        int cnt=0;//记录一下i的倍数出现的次数
        for(int j=i;j<N;j+=i)//从i开始枚举它的倍数出现的次数
        {
            cnt+=a[j];//记录一下
        }
        if(cnt>=3) //如果次数大于等于3，输出并跳出循环
        {
            cnt=0;
            for(int j=i;j<N&&cnt<3;j+=i)
                for(int d=0;d<a[j]&&cnt<3;d++,cnt++)
                    cout<<j<<" ";
            break;
        }
    }
    return 0;

}

这里我们的代码实现将三个数的最大公约数直接转化成了一个数的倍数有三个（其实就是一个转化问题，问三个数的最大公约数，并给定你范围，那么其实就是要你在这个范围内找到最大的能满足三个倍数的数字），可以说还是很巧妙的，然后我们从小的数字向大的数字输出，刚好满足了题目要求的字典序最小。