自己免费做网站的流程,响应式布局代码怎么写,怎么禁用wordpress谷歌字体,韩国能否出线题干#xff1a;
F先生有n个正整数#xff0c;a1#xff0c;a2#xff0c;...#xff0c;an
他认为这些整数的最大公约数太小了,所以他想通过删除一些整数来扩大它
您的任务是计算需要删除的最小整数数,以便剩余整数的最大公约数大于所有整数的公约数.
Input
3 1 2 4…题干
F先生有n个正整数a1a2...an
他认为这些整数的最大公约数太小了,所以他想通过删除一些整数来扩大它
您的任务是计算需要删除的最小整数数,以便剩余整数的最大公约数大于所有整数的公约数.
Input
3 1 2 4
Output
1
Input
4 6 9 15 30
Output
2
Input
3 1 1 1
Output
-1
题目大意
n个数要你删掉最少的数使得剩下的数的gcd大于所有n个数的gcd。 n3*10^5, 1ai1.5*10^7 解题报告
从gcd入手考虑gcd的本质是什么不过就是所有n个数的公因子。所以可以想到可以从枚举公因子的角度出发。
把所有的数都除以它们的gcd那么这n个新数的gcd一定为1常见套路则问题变为删掉最少的数使得它们的gcd不等于1。假设所有数都等于1显然无解。假设某一数不等于1则只保留最大的这一个数 就是一个解 所以一定有解。
我们先用cnt[i]表示a里面有多少个数等于i。
我们枚举保留下来的数的gcd为p则可以保留下来的个数为
可以发现因此我们枚举gcd的时候可以只枚举质数。可以通过线性筛将所有的质数O(n)时间复杂度筛出来
最后那个枚举的复杂度分析 AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 3e5 5;
const int MAXX 1e7 5e6 5;
int n,a[MAX],tot,p[MAXX],cnt[MAXX];
bool is[MAXX];
void prime() {memset(is,1,sizeof is);is[1]is[0]0;for(int i 2; iMAXX; i) {if(is[i] 0) continue;p[tot] i;for(int j ii; jMAXX; ji) {is[j] 0;}}
}
int main()
{int g0,ans 3e5;cinn;for(int i 1; in; i) scanf(%d,ai),g __gcd(g,a[i]);for(int i 1; in; i) cnt[a[i]/g];if(cnt[1] n) {cout -1 endl;return 0 ;}prime();for(int i 1; itot; i) {int sum 0;for(int j p[i]; jMAXX; jp[i]) {sum cnt[j];}ans min(ans,n-sum);}cout ans endl;return 0 ;
}
