又是毕业季I(Graduation Season I) 题解

思路分析

若选出的 $k$ 个互不相同的正整数的最大公约数为 $g$，则它们至少是 $1g, 2g, \dots, kg$，因此最大的一个至少为 $kg \le n$，即 $g \le \lfloor n / k \rfloor$。反之，直接取 $g = \lfloor n / k \rfloor$ 并选出 $g, 2g, \dots, kg$，其最大公约数恰好为 $g$。故答案即为 n / k，时间复杂度 $O(1)$。

参考代码

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, k;
    if (!(cin >> n >> k)) return 0;
    cout << (n / k) << "\n";
    return 0;
}