CF1925B 题解

yyrwlj · 2024-01-28 09:30:50 · 题解

题意简述

把一个正整数 x 分成 n 个正整数之和，让这 n 个正整数 的 \gcd 最大。

思路

不难猜想这 n 个正整数最好都是其中最小值的倍数，所以枚举 x 的约数就是枚举所有的最小值情况。

假设当前枚举的最小值是 i，因为要分成 n 个正整数，所以 x 至少要包含 n 个 i，也就是 \frac{x}{i} \ge n。

对于 x 的每一个满足上述条件的约数取最大值。

Code

#include <iostream>
using namespace std;
void work()
{
    int x, n;
    scanf("%d%d", &x, &n);
    int ans = 1;
    for (int i=1;i<=x/i;i++)
        if (x % i == 0)
        {
            if (x / i >= n)
                ans = max(ans, i);
            if (i != x / i && i >= n)
                ans = max(ans, x / i);
        }
    printf("%d\n", ans);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}