题目内容

P1372

大意:在 [1,n] 中选出 k 个数,求这 k 个数的最大的 gcd

解题思路

最近热爱写数论题不知道为什么

思路:当一个数是另一个数的倍数时,他们的 gcd 是其中小的那个数,因此想让 gcd 最大,这些选出来的数字必须满足倍数关系,又由于要选 k 个人,因此选出来人的编号应分别为 \lfloor n/k\rfloor2\lfloor n/k\rfloor3\lfloor n/k\rfloor ……所以最大的 gcd 应为 \lfloor n/k\rfloor。所以答案就是 \lfloor n/k\rfloor,复杂度 O(1)

代码:

#include <cstdio>

int main()
{
    int n,k;
    scanf("%d %d", &n, &k);
    printf("%d\n", n/k);
    return 0;
}
最后修改日期:2020年2月16日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。