题目内容

​ 小塔有一个长度为n的数组$[a1,a2,...,an]$。他定义一个中所有数的最小公倍数$lcm$不数组$x$是好的,当且仅当数存在于$x$中。例如，数组$[1,2,3,4]$是一个好数组，因为所有元素的$lcm=12$,而$12$不在数组中，所以它是一个好数组;而数组$[2,6,3]$不是好数组，因为所有元素的$lcm=6$,而$6$存在于数组中。 小塔希望从$a$中选择一个子序列，使得此子序列是好数组，并且他想知道子序列的最大长度。 如果数组$a$可以通过删除数组$b$中的若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子序列。

思路

  此题有一个很明显的条件那就是如果一个数组中所有数的lcm在这个数组中，那这个数一定是最大的数，因为lcm一定是大于等于所有数的，所以可以从贪心的角度去考虑，首先如果整个数组的lcm等于最大的数，那么就去删掉这个最大的数，继续观察剩下的数，重复操作，至于为什么可以直接删除最大的数，因为当所有数的lcm等于最大的数时，其他的数一定是最大数的因子，只有删掉最大的数，lcm才会变化，所以删除最大的数一定最优，实现时可以反向操作，那便是从小到大的加数

代码

c++

#include<iostream>
#include<cstring>
#include<cstdio>
#include<bits/stdc++.h>