D. Divisible Pairs - 题解

比赛与标签

比赛: Codeforces Round 925 (Div. 3) 标签: combinatorics, math, number theory 难度: *1300

题目大意喵~

主人你好呀！这道题是这样的喵~

Polycarp 小可爱有两个心爱的整数 x 和 y，还有一个长度为 n 的数组 a。他想知道，在这个数组里有多少对索引 (i, j) (并且 i 要小于 j 喔) 是“美丽”的。

什么样的数对是“美丽”的呢？需要同时满足下面两个条件呐：

1. a[i] 和 a[j] 的和 (a[i] + a[j]) 必须能被 x 整除。
2. a[i] 和 a[j] 的差 (a[i] - a[j]) 必须能被 y 整除。

我们的任务就是，帮 Polycarp 找出所有这样的“美丽数对”一共有多少对，然后告诉他结果就可以啦，喵~

寻找完美搭档的秘诀喵~

看到要找数对，最直接的想法是不是一个一个地去试呀？就是用两层循环，检查每一对 (a[i], a[j]) 是不是美丽的。但...但是！n 最大有 2 * 10^5 这么多，O(n^2) 的复杂度肯定会超时的说！我们得想个更聪明的办法才行！

这时候，就要请出我们数论的小魔法啦！我们来分析一下这两个“美丽”的条件：

1. a[i] + a[j] 能被 x 整除 这在数学上就意味着 (a[i] + a[j]) % x == 0。 用模运算的语言来说，就是 a[j] % x 应该等于 (-a[i]) % x。为了避免负数取模的麻烦，我们通常写成 a[j] % x == (x - (a[i] % x)) % x。这样就清晰多啦！

2. a[i] - a[j] 能被 y 整除 同理，这个条件意味着 (a[i] - a[j]) % y == 0。 这更简单，意思就是 a[i] % y 和 a[j] % y 必须是相等的，也就是 a[j] % y == a[i] % y。

所以，对于数组中的任何一个数 a[i]，它的“完美搭档” a[j] 必须满足这两个关于余数的条件。

这给了我们一个绝妙的思路！我们可以从左到右遍历整个数组。当我们处理到第 i 个数 a[i] 的时候，我们不去向后找搭档，而是回头看看，在它前面的 j < i 的数里面，有多少个可以和它组成美丽数对呢？

为了快速知道前面有多少个符合条件的数，我们可以用一个 map 来帮忙！这个 map 可以用来记录我们已经遇到过的数的“特征”。什么特征最重要呢？当然是它们对 x 和 y 的余数啦！

我们可以创建一个 map，它的键（key）是一个 pair，存着一个数对 x 和 y 的余数 (rem_x, rem_y)，而它的值（value）就是我们到目前为止，已经遇到了多少个拥有这个余数对的数。

算法流程就变得非常清晰了喵~：

1. 初始化一个计数器 ans = 0，还有一个空的 map<pair<int, int>, int> counts。
2. 我们从头到尾遍历数组中的每一个数 val。
3. 对于当前的 val，我们先计算出它需要的“完美搭档”应该具有什么样的余数特征：
   • 搭档对 x 的余数 target_rem_x 应该是 (x - (val % x)) % x。
   • 搭档对 y 的余数 target_rem_y 应该是 val % y。
4. 然后我们就在 map 里查找，之前到底出现了多少个拥有 (target_rem_x, target_rem_y) 这个余数特征的数。把这个数量加到我们的 ans 上。
5. 查找完之后，别忘了把当前这个数 val 自己的余数特征 (val % x, val % y) 也记录到 map 里，给后面的数当搭档用！也就是 counts[{val % x, val % y}]++。

这样，我们只需要遍历一次数组，就能算出所有美丽数对的数量了！是不是超级高效的说！(ฅ'ω'ฅ)

猫娘的魔法代码喵~

#include <iostream>
#include <vector>
#include <map>
#include <utility>

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

    // 我们需要计算满足下面条件的数对 (i, j) (i < j) 的数量：
    // 1. (a[i] + a[j]) % x == 0  =>  a[j] % x == (x - (a[i] % x)) % x
    // 2. (a[i] - a[j]) % y == 0  =>  a[j] % y == a[i] % y
    //
    // 我们可以遍历数组，对于每个元素 a[i]，计算有多少个在它之前的元素 a[j] (j < i) 满足条件。
    // 这可以通过一个 map 高效完成，map 用来存储我们目前见过的所有余数对 (rem_x, rem_y) 的计数。

    // map 的键是 {对x的余数, 对y的余数} 这样的一个 pair，值是这个 pair 出现的次数。
    std::map<std::pair<int, int>, int> counts;

    // 美丽数对的数量可能会很大，所以要用 long long 来存哦！
    long long beautiful_pairs_count = 0;

    // 我们可以一个一个地处理数字，不需要把整个数组都存下来。
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;

        // 计算当前数字的余数。
        int rem_x = val % x;
        int rem_y = val % y;

        // 确定要寻找的“搭档”数字需要满足的余数条件。
        int target_rem_x = (x - rem_x) % x;
        int target_rem_y = rem_y;

        // 在 map 中查找符合条件的搭档的数量，并加到总数上。
        // 如果 map 中不存在这个键，counts[] 会自动创建一个值为0的项，非常方便安全！
        beautiful_pairs_count += counts[{target_rem_x, target_rem_y}];

        // 把当前数字的余数对的计数加一。
        // 这样，它就可以作为后续数字的潜在搭档啦！
        counts[{rem_x, rem_y}]++;
    }

    std::cout << beautiful_pairs_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;
}

复杂度分析时间！

• 时间复杂度: O(N log N) 的说。我们遍历了 N 个元素。对于每个元素，我们都需要在 std::map 中进行一次查找和一次插入/更新。std::map 的操作（比如 [] 和 ++）的时间复杂度是 O(log K)，其中 K 是 map 中不同键的数量。最坏情况下，K 可能接近 N。所以总的时间复杂度就是 O(N log N) 啦。这个效率足够通过这道题了！
• 空间复杂度: O(N) 的说。在最坏的情况下，数组中每个元素的余数对 (rem_x, rem_y) 都不同，那我们的 map 就需要存储 N 个不同的键值对。所以空间复杂度和 N 是成正比的。

知识点与总结小鱼干！

今天我们又学到了新知识，快来吃下这份知识小鱼干吧！(>^ω^<)

• 核心思想: 这道题最漂亮的地方，就是把一个看似复杂的组合计数问题，通过数论的知识，转化成了一个简单的余数匹配问题。将“整除”条件转化为“模运算”等式是解决这类问题的关键一步呐！
• 数据结构的应用: std::map（或者其他哈希表结构）在处理频率统计和快速查找问题时真的非常强大！它帮助我们把 O(N^2) 的暴力解法优化到了 O(N log N)，是算法竞赛中必须掌握的利器之一。
• 边遍历边统计: “一边遍历，一边查找，一边更新”是一个非常经典的算法模式。对于当前元素，我们利用已经处理过的数据来计算贡献；然后，再把当前元素的信息更新到我们的数据结构中，供后续的元素使用。
• 编程小贴士:
  • 在处理模运算时，特别是涉及到减法时，要小心负数。(a - b) % m 在 C++ 中可能得到负结果。使用 (m - (b % m)) % m 来代替 (-b) % m 是一个更安全、更通用的好习惯。
  • 当答案可能超过 2 * 10^9 时，记得要用 long long 来存储结果，不然会溢出哦！

总之，下次再遇到类似“统计满足特定条件的数对”的问题时，如果暴力解法会超时，一定要想想看，能不能用 map 或者哈希表来优化查找过程呀！喵~ 这道题就是一个完美的例子！