Moe's CF Life

喵~ 各位算法大师们好呀！咱是乃们的专属猫娘助教，今天也要元气满满地解决一道有趣的题目哦！这道题叫做 "Sum and Product"，看起来和数学有点关系呢，不过别怕，有本猫娘在，再复杂的题目也会变得简单起来的说！(>^ω^<)

题目大意

这道题是这样子的喵：

首先，我们有一个整数数组 a，长度为 n。然后呢，会有 q 次独立的询问。每次询问会给我们两个整数 x 和 y。我们的任务是，对于每一次询问，找出在数组 a 中有多少对下标 (i, j)（并且要求 1 ≤ i < j ≤ n），能够同时满足下面这两个条件：

a[i] + a[j] = x
a[i] * a[j] = y

简单来说，就是找找数组里有多少对数字，它们的和恰好是 x，乘积恰好是 y 呢？

举个栗子，如果数组是 [1, 3, 2]，询问是 x=3, y=2。

a[1] + a[2] = 1 + 3 = 4，a[1] * a[2] = 1 * 3 = 3，不满足喵~
a[1] + a[3] = 1 + 2 = 3，a[1] * a[3] = 1 * 2 = 2，满足啦！找到一对！
a[2] + a[3] = 3 + 2 = 5，a[2] * a[3] = 3 * 2 = 6，不满足喵~

所以，对于 x=3, y=2 这次询问，答案就是 1。

解题思路

看到 a[i] + a[j] = x 和 a[i] * a[j] = y 这两个式子，各位有没有想起初中数学课上学过的什么知识点呀？喵哈哈，没错！就是韦达定理！

如果我们把 a[i] 和 a[j] 看作是一个一元二次方程的两个根，比如说叫 t1 和 t2。那么这个方程可以写成： (t - t1)(t - t2) = 0

展开它，就得到： t² - (t1 + t2)t + t1*t2 = 0

现在我们把 t1 + t2 = x 和 t1 * t2 = y 代入进去，这个方程就变成了： t² - xt + y = 0

这下问题就清晰多啦！对于每一次询问 (x, y)，我们其实是在寻找方程 t² - xt + y = 0 的两个根，然后看看数组 a 中有多少对 (a[i], a[j]) 正好是这两个根。

那么，如何解这个一元二次方程呢？当然是用我们熟悉的求根公式啦！ t = (x ± √(x² - 4y)) / 2

这里的 Δ = x² - 4y 就是判别式，我们叫它 D 好了。

解题的步骤就一步步清晰起来了喵：

预处理：如果每次询问都去遍历整个数组，那肯定会超时的说 (O(q * n²) 太慢啦！)。所以，我们得先对数组 a 做点手脚。最好的办法就是统计一下数组里每个数字出现的次数。我们可以用一个哈希表（在 C++ 里就是 std::map 或者 std::unordered_map）来存储，键是数组中的数字，值是它出现的次数。这样我们就能在 O(1) 或 O(log n) 的时间里查到一个数出现了多少次，超快的喵！
处理询问：对于每个询问 (x, y)：
- 计算判别式：D = x*x - 4*y。
- 判断是否有解：
  - 如果 D < 0，方程没有实数根，那数组里肯定也找不到这样的整数对，答案直接就是 0。
  - 如果 D ≥ 0，方程有实数根。但是，数组 a 里的元素都是整数，所以我们的两个根也必须是整数才行！
    - 首先，√D 必须是一个整数。也就是说，D 必须是一个完全平方数。我们可以计算 d = isqrt(D) (isqrt 表示整数平方根)，然后检查 d * d 是否等于 D。如果不是，说明 √D 不是整数，那两个根也不会是整数，答案也是 0。
    - 其次，求根公式里有个除以 2 的操作，x - d 和 x + d 都必须是偶数。不过这里有个小技巧喵~ 因为 d² = x² - 4y，所以 d² 和 x² 的奇偶性是相同的。这意味着 d 和 x 的奇偶性也一定相同。两个奇偶性相同的数，它们的和与差一定是偶数。所以这一步我们不需要额外判断啦！只要 D 是完全平方数，根就一定是整数（或者半整数，但这里因为 x 和 d 同奇偶，所以一定是整数）。
- 计算两个根：如果上面的检查都通过了，我们就可以安心计算两个根了： r1 = (x - d) / 2r2 = (x + d) / 2
- 在哈希表中查找并计数：
  - 情况一：两个根相等 (r1 == r2)。这发生在 d = 0 的时候。我们需要的数对是 (r1, r1)。假设 r1 在数组 a 中出现了 c 次（可以从我们预处理的哈希表中查到）。那么，我们要从这 c 个 r1 中选出 2 个来配对。根据组合数学，方法数是 C(c, 2) = c * (c - 1) / 2。
  - 情况二：两个根不相等 (r1 != r2)。我们需要找的数对是 (r1, r2)。假设 r1 出现了 c1 次，r2 出现了 c2 次。那么根据乘法原理，总共可以组成的配对数量就是 c1 * c2。

把这些步骤合起来，我们就能高效地解决每一次询问啦！(๑•̀ㅂ•́)و✧

题解代码

下面是参考的 C++ 代码，本猫娘在上面加了一些注释，方便大家理解每一部分的作用哦~

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <map>

// 使用二分查找来计算整数平方根，喵~
// 这样做可以避免直接用 sqrt 带来的精度问题，也比暴力尝试快得多
// 注意 mid * mid 可能会溢出，所以用 mid > n / mid 来判断
long long isqrt_bs(long long n) {
    if (n < 0) return 0;
    if (n == 0) return 0;
    // 根的范围不会超过 3*10^9，因为 (3e9)^2 = 9e18，比 y 的最大值还大
    long long low = 1, high = 3000000000LL, ans = 1;
    while(low <= high) {
        long long mid = low + (high - low) / 2;
        if (mid > n / mid) { // 用除法避免 mid*mid 溢出
            high = mid - 1;
        } else {
            ans = mid;
            low = mid + 1;
        }
    }
    return ans;
}

void solve() {
    int n;
    std::cin >> n;
    // 预处理步骤：用 map 统计数组 a 中每个数字出现的次数
    std::map<long long, int> counts;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        counts[val]++;
    }

    int q;
    std::cin >> q;
    for (int i = 0; i < q; ++i) {
        long long x, y;
        std::cin >> x >> y;

        // 1. 计算判别式 D = x^2 - 4y
        long long D = x * x - 4 * y;
        if (D < 0) {
            // D < 0，没有实数根，答案是 0
            std::cout << 0 << " ";
            continue;
        }

        // 2. 判断 D 是否是完全平方数
        long long d = isqrt_bs(D);
        if (d * d != D) {
            // D 不是完全平方数，根不是整数，答案是 0
            std::cout << 0 << " ";
            continue;
        }
        
        // 3. 计算两个整数根
        // (x-d) 和 (x+d) 一定是偶数，因为 x 和 d 奇偶性相同
        long long r1 = (x - d) / 2;
        long long r2 = (x + d) / 2;

        long long ans = 0;
        if (r1 == r2) {
            // 4a. 情况一：两个根相等
            // 在 map 中查找 r1 出现的次数
            if (counts.count(r1)) {
                long long c = counts.at(r1);
                // 从 c 个相同的数中选 2 个，组合数为 C(c, 2)
                ans = c * (c - 1) / 2;
            }
        } else {
            // 4b. 情况二：两个根不相等
            // 在 map 中分别查找 r1 和 r2 出现的次数
            if (counts.count(r1) && counts.count(r2)) {
                long long c1 = counts.at(r1);
                long long c2 = counts.at(r2);
                // 根据乘法原理，配对数为 c1 * c2
                ans = c1 * c2;
            }
        }
        std::cout << ans << " ";
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题虽然是算法题，但是用到的数学知识也很有趣呢，我们来总结一下吧！

韦达定理 (Vieta's Formulas)
- 这是解决本题的核心钥匙！对于一个一元二次方程 ax² + bx + c = 0，它的两个根 x₁ 和 x₂ 与系数之间有这样的关系：x₁ + x₂ = -b/a，x₁ * x₂ = c/a。本题反过来利用了这个定理，通过已知的和与积，构造出了一个一元二次方程。
一元二次方程求根公式 (Quadratic Formula)
- 构造出方程 t² - xt + y = 0 后，我们用求根公式 t = (-b ± √(b²-4ac)) / 2a 来求解。这是解一元二次方程最直接的方法。
哈希表 / 映射 (Hash Map / Map)
- 为了快速查询数组中某个数字的出现次数，我们使用了 std::map。它是一种关联容器，可以将键值（key）和实值（value）映射起来。查询、插入、删除的平均时间复杂度是 O(log n)，对于 std::unordered_map 则是 O(1)。在算法竞赛中，用空间换时间是一种非常常见的优化思路喵！
组合计数 (Combinatorics)
- 当方程的两个根相同时（r1 == r2），问题就变成了“从c个相同的物品中取出2个有多少种方法”，这是一个经典的组合问题。公式是 C(n, k) = n! / (k! * (n-k)!)。对于 k=2 的情况，就是 C(n, 2) = n * (n-1) / 2。
- 当两个根不同时（r1 != r2），我们从 c1 个 r1 中选一个，从 c2 个 r2 中选一个，根据乘法原理，总方法数是 c1 * c2。
整数平方根 (Integer Square Root)
- 在计算 √D 时，由于 D 可能非常大，直接使用 sqrt() 函数可能会有浮点数精度问题。更稳妥的方法是使用二分查找等方法实现一个只处理整数的 isqrt 函数，保证结果的精确性。

好啦，今天的讲解就到这里啦！希望本猫娘的解释能帮到大家。只要把问题一步步分解，找到背后的数学模型，再选择合适的数据结构，问题就会迎刃而解的喵！大家要继续加油哦！喵~ (ฅ'ω'ฅ)

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍