ACdream OJ 1153 (k-GCD)
gcd OJ
2023-09-14 09:07:57 时间
题目链接:
http://115.28.76.232/problem?pid=1153
题意:
从给定的n个数中取出k个数,使得他们的最大公约数最大,求这个最大的公约数
分析:
暴力分解不可取,我们能够得到最大公约数肯定在[1,mmax]之间(mmax为当中最大的元素),因为mmax不大,
因此我们能够从大到小枚举公约数,然后统计它的倍数的个数是不是大于等于k。假设是的话那么这个数必定是最大的。
代码例如以下:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 10010; int a[maxn]; int main() { int n,k,t,x; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); memset(a,0,sizeof(a)); int mmax = 0; for(int i=0;i<n;i++){ scanf("%d",&x); a[x]++; if( x > mmax) mmax = x; } int ans; bool f=0; for(int i=mmax;i>=1;i--){ int cnt=0; for(int j=i;j<=mmax;j+=i){ cnt += a[j]; if(cnt>=k){ ans = i; f=1; break; } } if(f) break; } printf("%d\n",ans); } return 0; }
相关文章
- 【题解】gcd区间(ST表)
- c语言oj平台作业,OJ平台C语言习题答案.pdf
- P2257 YY的GCD
- 蓝桥杯算法训练 最大体积 (gcd+完全背包)------C语言—菜鸟级
- gcd exgcd[通俗易懂]
- GCD Determinant 解题报告
- C++ 最大公约数 Greatest Common Divisor GCD
- Maximum GCD(UVA 11827)
- iOS 多线程:『GCD』详尽总结(二)
- iOS 多线程:『GCD』详尽总结(一)
- 多线程——GCD
- GCD 串行队列
- GCD 并发队列
- 多线程—GCD
- iOS开发中GCD在多线程方面的理解详解手机开发
- GCD的常用方法总结详解手机开发
- 【swift】BlockOperation和GCD实用代码块详解手机开发