喵~ 各位算法爱好者们，大家好呀！我是你们最喜欢的小猫娘，今天也要元气满满地解决一道有趣的题目哦！ฅ'ω'ฅ

今天我们要一起探险的题目是 D. Buying Shovels，一个关于怎么买铲子最划算的问题。听起来就很实用，对吧？那么，让我们一起来看看吧！

题目大意

Polycarp 同学想要买正好 n 把铲子。商店里有 k 种不同规格的铲子包，第 i 种规格的包装着 i 把铲子（1 ≤ i ≤ k）。每种规格的铲子包都有无限多个。

现在，Polycarp 必须做出一个决定：他要选择一种包装规格，然后购买若干个（至少一个）这种规格的包，最终目标是不多不少，正好买到 n 把铲子。

我们的任务就是，帮他计算一下，要满足这些条件，他最少需要买多少个包裹呢？

举个栗子：如果 n = 8，k = 7。

• 他可以选择大小为 1 的包，买 8 个。
• 他可以选择大小为 2 的包，买 4 个。
• 他可以选择大小为 4 的包，买 2 个。
• 他不能选择大小为 8 的包，因为 8 > k（k=7）。 在这些选择中，买 2 包是数量最少的。所以答案就是 2。

解题思路

这个问题看起来有点复杂，但让本猫娘来分析一下，你就会发现它的本质其实非常简单哦，喵~

1. 数学建模： 我们设定 Polycarp 选择的铲子包规格大小为 s，购买的包裹数量为 c。根据题意，他总共要买 n 把铲子，所以必须满足下面的等式： s * c = n

2. 挖掘约束条件：

   • 从上面的等式我们可以看出，s 必须是 n 的一个约数（或者叫因数）。
   • 题目还规定，铲子包的规格 s 不能随便选，必须是商店里有的，也就是 1 ≤ s ≤ k。
   • 我们的目标是，让购买的包裹数量 c 最小化。

3. 找到最优解： 根据 c = n / s 这个关系式，要想让 c 变得最小，我们只需要让分母 s 变得最大就好了！

   所以，问题就转化成了一个非常清晰的目标：找到 n 的所有约数中，那个小于等于 k 的最大约数！ 喵~

   我们把这个最大的、符合条件的约数叫做 s_max。那么最终的答案就是 n / s_max 啦！

4. 如何找到这个 s_max 呢？ 我们需要遍历 n 的所有约数。一个非常高效的方法是只遍历到 sqrt(n)（n的平方根）。

   • 我们从 i = 1 开始循环，直到 i * i ≤ n。
   • 在循环中，如果 i 能整除 n（也就是 n % i == 0），那么我们就找到了一个约数 i。
   • 与此同时，n / i 也一定是 n 的一个约数！就像找到了一对小鱼干，一网打尽！(´｡• ᵕ •｡`)
   • 对于找到的每一对约数（i 和 n/i），我们都检查它们是否小于等于 k。如果是，就用它来更新我们记录的 s_max。

   循环结束后，s_max 就是我们梦寐以求的那个“最大的、且不大于k的”约数啦！

题解代码

这是用 C++ 实现的代码，加上了本猫娘的思路注释哦~

#include <iostream>
#include <algorithm>

// 这个函数用来解决单个测试用例，喵~
void solve() {
    long long n, k;
    std::cin >> n >> k;

    // 我们的目标是买正好 'n' 把铲子。
    // 假设我们选择的铲子包大小是 's'，买了 'c' 包。
    // 那么 s * c = n。
    // 这意味着 's' 必须是 'n' 的一个约数。
    // 我们买的包裹数 c = n / s。
    // 为了让 'c' 最小，我们必须让 's' 最大。
    //
    // 对 's' 的限制是：
    // 1. 's' 必须是 'n' 的约数。
    // 2. 1 <= s <= k。
    //
    // 所以，我们的任务就是找到 'n' 的约数中，小于或等于 'k' 的那个最大的。
    // 设这个约数为 'max_s'，那么最少包裹数就是 n / max_s。

    long long max_s = 1; // 初始化为最小的可能约数 1。
                         // 因为 k>=1，所以大小为1的包总是合法的。

    // 我们通过遍历到 sqrt(n) 来高效地找到 'n' 的所有约数。
    for (long long i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            // 如果 'i' 是一个约数，那么 'n/i' 也是一个约数。
            long long d1 = i;
            long long d2 = n / i;

            // 检查约数 d1 是否是合法的铲子包大小。
            if (d1 <= k) {
                max_s = std::max(max_s, d1);
            }

            // 检查约数 d2 是否是合法的铲子包大小。
            if (d2 <= k) {
                max_s = std::max(max_s, d2);
            }
        }
    }

    // 最少包裹数 = n / (最大的合法铲子包大小)。
    std::cout << n / max_s << '\n';
}

int main() {
    // 快速 I/O，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

整数约数 (Integer Divisor)

如果一个整数 a 能被另一个非零整数 b 整除，我们就说 b 是 a 的约数（或因数）。例如，12 的约数有 1, 2, 3, 4, 6, 12。

高效寻找约数的方法：O(sqrt(n)) 算法

为什么我们只需要遍历到 sqrt(n) 就能找到所有约数呢？

这是因为约数总是成对出现的！(=^･ω･^=)

• 如果我们找到了一个约数 i，那么 n / i 也必然是 n 的一个约数。
• 如果 i < sqrt(n)，那么 n / i > sqrt(n)。
• 如果 i > sqrt(n)，那么 n / i < sqrt(n)。
• 如果 i = sqrt(n)，那么 n / i = i，这对约数是相等的。

所以，我们只需要检查从 1 到 sqrt(n) 的所有数 i。只要 i 是 n 的约数，我们就能同时得到 i 和 n/i 这一对约数。这样就覆盖了所有情况，不会有任何遗漏，而且速度非常快！

---

好啦，今天的铲子问题就愉快地解决啦！通过把问题转化为寻找最大的有效约数，我们就能轻松搞定它。是不是很简单呢？希望大家都能有所收获！下次再见啦，喵~ ( ´ ▽ ` )ﾉ