3116就是说对于coin先有各自的倍数然后再是公倍数如果找到coins当中共同的最小公倍数x后那么后面的所有数都是这个x的倍数但如果最小公倍数不存在coin当中呢或为1就无法组合或许二分搜索对于第k小的数它的上界一定为min(coin*k)那么在这个搜索区间内的对于每个数对于每个coin的numnum一定小于等于k对Num求和这个求和结果去逼近k那么关键在于num求和时的相同数字去重对于搜索数x对coin1为第num1的数对coin2为第num2的数找到coin1和coin2的最小公倍数y那么期间会重复x/y个数所以只有两个数的情况下对于x是所有情况下的第num1num2-x/y个数记为a如果a大于k说明x大了应该减小x如果a小于k说明x小了应该增大x之后如果coins的数量不为2那么就是两两组合它们如果有z个硬币那就有Cz2组合数量的公倍数再容斥定理去减掉还有就是说该寻找的是最小公倍数还是最大公约数对于[3,6,9]的组合对于多个数的组合还是有点难说就是得容斥定理对于三方的情况就是abc-d-e-f2g如果是四方或更多则更复杂这个数量的限制是15所以最多有15个可能互相发生重叠的部分那这个题的流程就是对于coins当中的所有数先两两三三全组合出来它们的最小公倍数即两个之间的三个之间的四个之间的....然后把lcm结果保存到一个数组当中以上是预处理之后再二分对某个搜索数x运用容斥定理去计算出一个结果不断去搜索质因数分解这样可以保证每个循环里的p都是可以分解出来的质数比如2增长到3都是质数到4时4一定不会被x整除因为如果可以整除那么在p2的时候就可以被整除了使其count了最大公约数为什么是取每个质因子出现的最小值以及如果有另一个数没出现过的质因子是取0还是1就是说每个数都是由质因数相乘组成的然后如果要求两个数所构成的最大公约数就必须满足这两个数质因数的要求即不能超过其最小质因数次数的限制否则一旦多的话就不能被那个组成数所整除a和b以及gcd与lcm关系求解这个就是说把a和b拆成质因数相乘后由于gcd和lcm都是分别取a和b的最小和最大次数相乘所得到的那么把它们乘在一起的结果也必然同时包含其质因数里的最大值和最小值因为就俩数不是最大值就是最小值那么也就是a和b的乘积