Moe's CF Life

喵哈~！各位master，今天由我来给大家讲解一道关于一元二次方程的数学题，nya~。这道题看起来有点复杂，但只要我们一步步拆解，就像小猫玩毛线球一样，总能找到线头的说！

E. Square Equation Roots

题目大意 (Problem Summary)

有一个可爱的小朋友 Petya 正在研究一元二次方程，方程的形式是 x² + 2bx + c = 0，其中 b 和 c 都是正整数。

Petya 对所有满足 1 ≤ b ≤ n 和 1 ≤ c ≤ m 的方程都非常感兴趣。他想知道，把这些方程所有的实数根都收集起来，放到一个集合里，去重之后，总共有多少个不同的实数根呢？

简单来说，就是要求所有方程 x² + 2bx + c = 0 (其中 1 ≤ b ≤ n, 1 ≤ c ≤ m) 的不同实数根的总数，喵~。

解题思路 (Solution Approach)

这道题的核心是“计数”和“去重”。一个很自然的想法是先算出所有根（包括重复的），然后再想办法把重复的部分去掉。这不就是伟大的容斥原理嘛！

最终答案 = (所有根的总数) - (被重复计算的根的总次数) + (所有不同种类的重复根的数量)

听起来是不是有点绕？让本喵给你解释一下~ 假设根 -1 出现了 3 次，根 -5 出现了 2 次。

所有根的总数：把这 3 个 -1 和 2 个 -5 都算上，总共 5 个。
被重复计算的根的总次数：根 -1 出现了 3 次，重复了 3-1=2 次；根 -5 出现了 2 次，重复了 2-1=1 次。所以总共重复了 2+1=3 次。
所有不同种类的重复根的数量：这里有两种重复根，-1 和 -5，所以是 2。
最终答案：5 - 3 + 2 = 4？不对不对，公式应该是这样的： 最终答案 = (所有根的总数) - (所有重复根的出现次数之和) + (不同重复根的种类数)5 - (3+2) + 2 = 2。对啦！就是 -1 和 -5 这两种。

所以，我们的任务就分成了三步，喵~

第一步：计算所有根的总数 (Total Roots)

首先，我们来解这个方程 x² + 2bx + c = 0。根据求根公式，根为： x = (-2b ± sqrt(4b² - 4c)) / 2 = -b ± sqrt(b² - c)

要有实数根，判别式 Δ' = b² - c 必须大于等于 0，也就是 c ≤ b²。

对于一个固定的 b (1 ≤ b ≤ n)：

c 的取值范围是 1 ≤ c ≤ m，同时要满足 c ≤ b²。所以 c 的有效范围是 1 ≤ c ≤ min(m, b²)。
当 c = b² 时，Δ' = 0，方程有一个实数根 x = -b。
当 c < b² 时，Δ' > 0，方程有两个不同的实数根 x = -b ± sqrt(b² - c)。

所以，对于一个固定的 b，它能产生的根的数量是：

有 min(m, b²) 个有效的 c 值。
其中一个值 c = b² (如果 b² ≤ m) 产生 1 个根。
另外 min(m, b²) - 1 个 c 值产生 2 个根。
总根数 = 1 * 1 + 2 * (min(m, b²) - 1) = 2 * min(m, b²) - 1 (这个公式在 b² > m 时不成立)。

我们换个思路，更简单一点喵~：

对于固定的 b，如果 b² > m，那么所有 c (1 到 m) 都满足 c < b²。所以有 m 个方程，每个方程产生 2 个根，总共 2 * m 个根。
如果 b² ≤ m，那么 c 的取值范围是 1 到 b²。其中 c = b² 产生 1 个根，c 从 1 到 b² - 1 (共 b²-1 个值) 产生 2 * (b² - 1) 个根。总共 1 + 2 * (b² - 1) = 2b² - 1 个根。

所以，所有根的总数 total_roots 就是把所有 b 的情况加起来： total_roots = Σ (当b²≤m时, 2b²-1) + Σ (当b²>m时, 2m) 我们可以找到一个临界点 t = floor(sqrt(m))。

当 b ≤ t 时，b² ≤ m。
当 b > t 时，b² > m。所以，我们把 b 从 1 到 n 的求和分成两部分：1 到 min(n, t) 和 min(n, t)+1 到 n。这样就可以高效地算出总根数啦！

第二步：找出哪些根会重复 (Finding Duplicates)

这是最关键的一步！什么时候两个不同的方程 (b₁, c₁) 和 (b₂, c₂) 会产生相同的根呢？

根的形式是 -b ± sqrt(b² - c)。令 d = b² - c，根就是 -b ± sqrt(d)。

如果根是无理数：比如 x = -b₁ ± sqrt(d₁)，其中 d₁ 不是完全平方数。如果它和另一个根 -b₂ ± sqrt(d₂) 相等，由于有理部分和无理部分必须分别相等（这是一个很重要的数论知识点哦！），那么必然有 b₁ = b₂，进而 d₁ = d₂，从而 c₁ = c₂。也就是说，无理根是唯一的，它只属于一个 (b, c) 对，不会被重复计算！
如果根是整数：啊哈！只有整数根才可能被不同的 (b, c) 对产生。假设有一个整数根 x = -k (其中 k > 0，因为 b, c > 0，根一定是负数)。把它代入方程：(-k)² + 2b(-k) + c = 0k² - 2bk + c = 0c = 2bk - k²
对于一个整数根 -k，只要我们能找到一个 b (1 ≤ b ≤ n)，使得 c = 2bk - k² 满足 1 ≤ c ≤ m，那么这个 (b, c) 对就能产生整数根 -k。
所以，我们要做的就是：
- 遍历所有可能的整数根 -k。
- 对于每个 -k，计算有多少个 b 能够满足 1 ≤ 2bk - k² ≤ m。
- 这个 b 的数量，就是根 -k 的出现次数 N_k。
从不等式 1 ≤ 2bk - k² ≤ m，我们可以解出 b 的范围： b ≥ (k² + 1) / (2k)b ≤ (k² + m) / (2k) 再结合 1 ≤ b ≤ n，我们就能确定 b 的所有可能取值，从而算出 N_k。

第三步：容斥原理大显神威 (Inclusion-Exclusion)

现在我们有了所有需要的东西啦：

total_roots：所有根的总数（计重）。
total_occ：所有整数根的出现次数总和，即 Σ N_k。
D_count：不同整数根的种类数，即 N_k > 0 的 k 的数量。

根据我们一开始的容斥公式： 最终答案 = total_roots - total_occ + D_count

举个栗子：total_roots 计算了 -1 三次，-5 两次。 total_occ 就是 3 + 2 = 5。 D_count 就是 2。 total_roots - 5 + 2 相当于从总数里，把 -1 的贡献减去 3 再加回 1，把 -5 的贡献减去 2 再加回 1。正好每个都只算了一次！完美，喵~

题解代码 (Solution Code)

cpp

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    // 使用C++标准IO加速，让程序跑得更快，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m;
    cin >> n >> m;

    // 步骤一：计算所有根的总数 (total_roots)
    // t_val 是 sqrt(m) 的整数部分，是 b² ≤ m 和 b² > m 的分界线
    long long t_val = sqrt(m);
    // 稍微修正一下 t_val，确保 (t_val+1)² > m
    if ((t_val + 1) * (t_val + 1) <= m) {
        t_val++;
    }

    long long total_roots = 0;
    // b 的范围是 1 到 n，t_val 是临界点，所以我们先处理到 min(n, t_val)
    long long lim = min(n, t_val);

    // 对于 b ≤ t_val, b² ≤ m, 每个 b 贡献 2*b²-1 个根
    for (long long b_val = 1; b_val <= lim; b_val++) {
        total_roots += 2 * b_val * b_val - 1;
    }
    // 对于 b > t_val, b² > m, 每个 b 贡献 2*m 个根
    if (n > t_val) {
        total_roots += 2 * m * (n - t_val);
    }

    // 步骤二和三：计算整数根的重复情况
    long long total_occ = 0; // 所有整数根的出现次数之和
    long long D_count = 0;   // 不同整数根的种类数

    // 遍历所有可能的整数根 -k。k 的上限为什么是 2n-1？
    // 因为 c = 2bk - k² ≥ 1, b ≤ n => 2nk > k² => k < 2n。
    for (long long k = 1; k <= 2 * n; k++) {
        // b 的下界是 ceil((k²+1)/(2k))
        long long b_min = (k * k + 1 + 2 * k - 1) / (2 * k);
        // b 的上界是 floor((k²+m)/(2k))
        long long b_max = (k * k + m) / (2 * k);

        // b 的实际范围要和 [1, n] 取交集
        long long L = max(1LL, b_min);
        long long R = min(n, b_max);

        long long occ = 0; // 根 -k 的出现次数
        if (R >= L) {
            occ = R - L + 1;
        }

        if (occ > 0) {
            total_occ += occ; // 累加到总出现次数
            D_count++;        // 发现一种新的重复根
        }
    }
    
    // 最终答案 = 总根数 - 重复根总次数 + 重复根种类数
    long long distinct_roots = total_roots - total_occ + D_count;
    cout << distinct_roots << endl;

    return 0;
}

注意: 提供的原始题解代码在计算 occ 时分成了 count1, count2, overlap 三部分，逻辑稍微复杂一些，但本质上也是在计算满足条件的 b 的数量。我在这里给出的简化版代码，其核心思想是相同的，都是通过 c = 2bk - k² 来找到整数根的出现次数，更容易理解一些，喵~。两种写法都能得到正确答案。

E. Square Equation Roots ​

题目大意 (Problem Summary) ​

解题思路 (Solution Approach) ​

第一步：计算所有根的总数 (Total Roots) ​

第二步：找出哪些根会重复 (Finding Duplicates) ​

第三步：容斥原理大显神威 (Inclusion-Exclusion) ​

题解代码 (Solution Code) ​

相关知识点 (Knowledge Points) ​