A Balanced Problemset?

题面翻译

题意简述

有一个序列，已知其和为 $X$，长度为 $N$，求这个序列最大的最大公因数。

输入格式

第一行有一个整数 $T$，有 $T$ 组数据。

接下来 $T$ 行，每行两个整数，分别为 $X,N$。

输出格式

每组数据输出一行，表示可能的最大公因数。

题目描述

Jay managed to create a problem of difficulty $ x $ and decided to make it the second problem for Codeforces Round #921.

But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of $ n $ sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to $ x $ .

The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.

Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.

输入格式

The first line of input contains a single integer $ t $ ( $ 1\leq t\leq 10^3 $ ) denoting the number of test cases.

Each test case contains a single line of input containing two integers $ x $ ( $ 1\leq x\leq 10^8 $ ) and $ n $ ( $ 1\leq n\leq x $ ).

输出格式

For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

样例 #1

样例输入 #1

3
10 3
5 5
420 69

样例输出 #1

2
1
6

提示

For the first test case, one possible way is to break up the problem of difficulty $ 10 $ into a problemset having three problems of difficulties $ 4 $ , $ 2 $ and $ 4 $ respectively, giving a balance equal to $ 2 $ .

For the second test case, there is only one way to break up the problem of difficulty $ 5 $ into a problemset of $ 5 $ problems with each problem having a difficulty $ 1 $ giving a balance equal to $ 1 $ .

首先想到能不能x/n除尽，能除尽最优，如果除不尽，有余数，那就让除数（i）减一（i–），余数加n，再看看余数加的这几个可不可以把当前（i）的除尽，但是这样会超时，但是都这样想了，就会发现余数加的值如果是i的倍数，就可以把i除尽，这样的话i就是最大的最大公约数，又可以发现，他们的总和是x，这满足这一情况的就是x的约数，就看看x的除以他的约数，有几个，能不能把n填满(>=n)，

开根号求所有约数

void solve()
{
    int x, n;
    cin >> x >> n; 
    int ans = 1;

    for (int i = 1; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            int a1 = x / i;
            int a2 = x / (x / i);
            if (a1 >= n) ans = max(ans, i);
            if (a2 >= n) ans = max(ans, x/i);
            //ans = max(ans, max(a1, a2));
        }
    }
    cout << ans << '\n';
}