Moe's CF Life

喵~ 主人，你好呀！我是你的专属猫娘助手，今天也要一起努力学习算法喵！(ฅ'ω'ฅ)

这次我们要看的题目是 Codeforces 1485C - Floor and Mod，一个关于整除和取模的有趣问题呐。别担心，只要跟着我的思路，再难的题目也会变得像小鱼干一样美味可口的！

题目大意

我们来一起看看题目说了什么吧，喵~

题目要求我们找一种叫做“特殊对”的东西。一对正整数 (a, b) 被称为“特殊对”，需要满足一个条件：⌊a/b⌋ = a mod b。

这里 ⌊a/b⌋ 表示 a 除以 b 的整数部分（向下取整），而 a mod b 是 a 除以 b 的余数。

现在，会给你两个整数 x 和 y，你的任务就是找出所有满足 1 ≤ a ≤ x 和 1 ≤ b ≤ y 的特殊对 (a, b) 的数量。

举个例子，如果 x=3, y=4：

我们来试试 (a,b) = (3,2)。
⌊3/2⌋ = 1
3 mod 2 = 1
它们相等！所以 (3,2) 是一个特殊对。
经过检查，这是唯一的一个，所以答案是 1。

是不是很简单呢？就是数数而已嘛！

解题思路

直接去遍历所有 a 和 b 的组合肯定是不行的啦，x 和 y 那么大，会超时的说！(>ω<) 我们需要更聪明的办法。

让本猫娘来施展一点小小的数学魔法吧！

关键的转换 我们从核心条件入手：⌊a/b⌋ = a mod b。让 k = ⌊a/b⌋ = a mod b。这样看起来就清爽多啦！
利用除法定义 根据整数除法的定义，任何一个正整数 a 都可以表示成 a = b * q + r，其中 q 是商，r 是余数。在这里，q = ⌊a/b⌋，r = a mod b。所以，我们可以把 a 写成：a = b * k + k。再整理一下，就是 a = k * (b + 1)。哇！a，b 和 k 的关系一下子就清晰起来了，喵！
分析 k 的范围k 是 a 除以 b 的余数，所以它必须满足 0 ≤ k < b。但是题目说了 a 和 b 是正整数。如果 k = 0，那么 a = 0 * (b+1) = 0，这不符合 a ≥ 1 的要求。所以，k 必须是正整数，k ≥ 1。结合起来，我们得到了一个至关重要的约束：1 ≤ k < b。这等价于 b ≥ k + 1。
汇总所有约束条件 现在我们把所有条件放在一起，看看对于一对 (a, b) 和一个 k，需要满足什么：
- a = k * (b + 1)
- 1 ≤ a ≤ x
- 1 ≤ b ≤ y
- b ≥ k + 1
改变枚举对象 与其枚举 a 和 b，我们不如枚举 k！为什么呢？我们来分析一下 k 的最大值。
- 我们有 a = k * (b + 1)
- 并且 b ≥ k + 1
- 那么，a = k * (b + 1) ≥ k * ((k + 1) + 1) = k * (k + 2)。
- 因为我们要求 a ≤ x，所以必须有 k * (k + 2) ≤ x。
- 这意味着 k² + 2k ≤ x。大致上，k² 不会超过 x，所以 k 的最大值约等于 sqrt(x)。
- x 最大是 10^9，那 sqrt(x) 大概是 31622 左右。这个范围非常小，完全可以遍历！真是个天才的发现，喵呜~
最终算法 我们的算法就出来啦：
- 遍历 k 从 1 开始，只要 k * (k + 2) ≤ x 就继续。
- 对于每一个固定的 k，我们来计算有多少个 b 满足条件。
- b 的条件是：
  1. b ≤ y （题目给的）
  2. b ≥ k + 1 （我们推导的）
  3. 从 a = k * (b + 1) ≤ x 可以得到 b + 1 ≤ x / k，也就是 b ≤ (x / k) - 1。
- 所以 b 必须满足：k + 1 ≤ b ≤ min(y, (x / k) - 1)。
- 只要这个区间的上界不小于下界，我们就可以计算出 b 的数量，然后加到总答案里。
- 对于一个 k，合法的 b 的数量就是 max(0, min(y, (x / k) - 1) - (k + 1) + 1)。

这样，我们只需要一个 O(sqrt(x)) 的循环就可以解决问题了，非常高效的说！

代码详解

下面让我们看看这份可爱的代码是怎么实现我们的思路的吧~

cpp

#include <iostream>
#include <algorithm>

void solve() {
    long long x, y;
    std::cin >> x >> y; // 读入 x 和 y，准备开始计算喵！

    long long count = 0; // 这是我们的计数器，用来装特殊对的数量

    // 我们要找的特殊对 (a,b) 满足 floor(a/b) = a % b
    // 设 k = floor(a/b) = a % b
    // 那么 a = k * b + k = k * (b + 1)
    // 并且作为余数，k 必须小于 b，即 1 <= k < b (因为 a,b > 0, k不能是0)

    // 我们来枚举 k 的值。
    // k 的下限是 1。
    // k 的上限是多少呢？因为 b >= k + 1，所以 a = k * (b + 1) >= k * (k + 2)。
    // 又因为 a <= x，所以 k * (k + 2) <= x。我们就用这个作为循环条件，可以大大减少枚举次数！
    for (long long k = 1; k * (k + 2) <= x; ++k) {
        // 对于一个固定的 k，我们要找到有多少个 b 满足条件。
        // b 的约束有：
        // 1. b > k                => b >= k + 1
        // 2. b <= y               (题目限制)
        // 3. a = k*(b+1) <= x     => b <= (x / k) - 1
        
        // 综合起来，b 的范围是 [k + 1, min(y, (x / k) - 1)]
        long long lower_bound_for_b = k + 1; // b 的下界
        long long upper_bound_for_b = std::min(y, (x / k) - 1); // b 的上界

        // 如果上界大于等于下界，说明存在合法的 b
        if (upper_bound_for_b >= lower_bound_for_b) {
            // 区间 [L, R] 中整数的个数是 R - L + 1
            count += (upper_bound_for_b - lower_bound_for_b + 1);
        }
    }

    std::cout << count << "\n"; // 输出我们找到的总数，任务完成！
}

int main() {
    // 这是一些加速输入输出的小魔法，让程序跑得更快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 多组测试数据
    while (t--) {
        solve();
    }

    return 0;
}

知识点小课堂

主人，学习完了解法，我们再来复习一下相关的知识点，这样才能记得更牢固哦！

整除与取模 (Integer Division and Modulo) 这是数论中最最基础的概念啦。对于任意整数 a 和正整数 b，总能唯一地找到整数 q 和 r，使得 a = b * q + r，并且 0 ≤ r < b。
- q 就是 a 除以 b 的商，在 C++ 中用 a / b 计算。
- r 就是 a 除以 b 的余数，在 C++ 中用 a % b 计算。这个关系 a = b * q + r 是解决这类问题的万能钥匙，一定要记住喵！
枚举与优化 (Enumeration and Optimization) 在算法竞赛中，当我们想不出什么高级数据结构或者神奇算法时，最朴素的想法就是枚举所有可能性。但直接枚举往往因为数据范围太大而超时。这时候，就需要对枚举进行优化。本题就是一个典型的例子：
- 朴素枚举：枚举 a 从 1 到 x，b 从 1 到 y，复杂度是 O(x*y)，太慢了。
- 优化枚举：通过数学变换，我们发现可以转而枚举一个中间量 k。k 的范围被约束在 O(sqrt(x))，使得整个算法的复杂度大大降低，变成了 O(sqrt(x))。这种“改变枚举对象”的思路非常常用，主人要掌握哦！

好啦，今天的讲解就到这里啦！主人是不是感觉收获满满呢？只要我们一起努力，没有什么问题是解决不了的！下次再见咯，喵~ ( ´ ▽ ` )ﾉ

题目大意 ​

解题思路 ​

代码详解 ​

知识点小课堂 ​

题目大意

解题思路

代码详解

知识点小课堂