[关闭]
@ysner 2018-06-08T14:19:28.000000Z 字数 870 阅读 1959

最大公约数

数论


题面

现有个数,询问选出个数的的最大值。

解析

枚举。

枚举最大值,看是否有个数能将其除尽。

话说我想了半天为什么不给出的范围,竟然没想到是因要开桶,的范围无意义。。。
于是我们开个桶记录每个数出现多少次。
然后枚举最大值。
要判断有多少个数能将其除尽,直接枚举即可。
复杂度最坏为


等价于

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=5e5+100;
  14. int n,k,a[N],ans=1,mx;
  15. int main()
  16. {
  17. freopen("gcd.in","r",stdin);
  18. freopen("gcd.out","w",stdout);
  19. n=gi();k=gi();
  20. fp(i,1,n)
  21. {
  22. re int x=gi();mx=max(mx,x);
  23. a[x]++;
  24. }
  25. fq(i,mx,1)
  26. {
  27. re int sum=0;
  28. for(re int j=1;j*i<=mx;j++) sum+=a[j*i];
  29. if(sum>=k) {printf("%lld\n",1ll*k*i);return 0;}
  30. }
  31. fclose(stdin);
  32. fclose(stdout);
  33. return 0;
  34. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注