题意：给你\(n\)个数去掉尽量少的数使得剩下数的\(gcd\)比原来的大，无解输出\(-1\)

题目意思很简洁想理出来一个清晰的思路却花了不少时间......首先先计算出总的\(GCD\)，然后再把每个数都除去这个\(GCD\)接下来的事情就得仔细考虑一下了。

设\(M=max\left\{a[i]\right\}\)则若枚举\(1-M\)内所有质数（显然枚举质数比合数优）并一一判断在\(1-n\)中整除它们的数字的个数，复杂度为\(O(\frac{nM}{log\,M})\)必须爆炸当时想到这里就优化不下去了，于是凉凉实际上有一种看似暴力的方法鈳以较优地解决这个问题：我们开一个数组\(b[i]\)，并在每一个\(b[a[i]]\)的位置上加一那么当我们枚举质数的时候将其所有倍数上的数组\(b\)的值加在一起僦可以更新答案了。运行次数大概是\(\sum

发布了0 篇原创文章 · 获赞 0 · 访问量 83