[hdu5207]Greatest Greatest Common Divisor

题目大意:给你n个数,从里面选2个,使得它们的最大公约数最大,输出这个最大公约数

题目链接

原本前一天在想一个相似的题目,但是是选k个,所以数据范围变小了,还是能用选k个的想法做。
思路很简单,首先由于这n个数不超过1e5,所以可以开个桶来存出现次数。
然后再从其中最大的数倒序枚举每一个自然数,再枚举自然数的倍数,如果这个自然数的倍数在桶里面出现不少于2次,这个自然数就是答案。

代码用了fread快读,所以目前在hdu这份代码是rank1 (78ms中提交时间最早的那一个)

代码

One thought to “[hdu5207]Greatest Greatest Common Divisor”

发表评论

电子邮件地址不会被公开。 必填项已用*标注