题目回顾

我们有一个长度为 $n$ 的数组 $a$，以及两个整数 $x$ 和 $y$。
一对下标 $(i, j)$ 满足 $1 \le i < j \le n$ 被称为 美丽对，当且仅当：

1. $a_i + a_j$ 能被 $x$ 整除；
2. $a_i - a_j$ 能被 $y$ 整除。

要求计算美丽对的数量。

---

条件转化

第一步：整除条件的等价形式

条件 1：

$$(a_i + a_j) \bmod x = 0$$

等价于：

$$(a_i \bmod x + a_j \bmod x) \bmod x = 0$$

因此：

$$a_i \bmod x + a_j \bmod x = 0 \quad \text{或} \quad x $$

即：

$$a_i \bmod x = (x - a_j \bmod x) \bmod x$$

条件 2：

$$(a_i - a_j) \bmod y = 0$$

等价于：

$$(a_i \bmod y - a_j \bmod y) \bmod y = 0$$

因此：

$$a_i \bmod y = a_j \bmod y$$

---

第二步：关键观察

对于固定下标 $j$，所有与 $j$ 构成美丽对的下标 $i$（$i < j$）必须同时满足：

$$a_i \bmod x = (x - a_j \bmod x) \bmod x$$

$$a_i \bmod y = a_j \bmod y$$

这意味着，如果我们把每个元素 $a_i$ 映射成一个键值对：

$$\text{key} = (a_i \bmod x,\; a_i \bmod y)$$

那么对于当前的 $a_j$，我们需要在之前出现过的元素中，找到所有键等于：

$$\left( (x - (a_j \bmod x)) \bmod x,\; a_j \bmod y \right) $$

的元素个数。

---

算法步骤

1. 初始化一个空字典（或哈希表）cnt，用来存储键值对 (a_i mod x, a_i mod y) 的出现次数。
2. 遍历数组 $a$ 中的每个元素 $e$（作为 $a_j$）：
   • 计算：$$xx = e \bmod x,\quad yy = e \bmod y$$
   • 计算需要的第一个余数：$$need\_x = (x - xx) \bmod x$$
   • 查询 cnt 中键 (need_x, yy) 的值，加到答案 ans 中。
   • 将当前元素对应的键 (xx, yy) 在 cnt 中的计数加 1。
3. 输出 ans。

---

时间复杂度

• 每个元素处理 $O(1)$ 次哈希表操作。
• 总复杂度 $O(n)$ 每个测试用例，所有测试用例总和 $O(\sum n)$，满足 $2 \times 10^5$ 的限制。

---

C++ 代码实现

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    map<pair<int, int>, int> cnt;
    long long ans = 0;
    
    for (int e : a) {
        int xx = e % x;
        int yy = e % y;
        
        int need_x = (x - xx) % x;
        ans += cnt[{need_x, yy}];
        
        cnt[{xx, yy}]++;
    }
    
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

示例验证

以题目第一个样例为例：

输入：

6 5 2
1 2 7 4 9 6

过程：

$e$	$xx$	$yy$	$need\_x$	匹配数	累计答案
1			4	0
2	2	0	3
7		1
4	4	0	1
9		1		1	1
6	1	0	4		2

输出 2，与题目一致。

---

总结

本题的核心在于将复杂的整除条件转化为对余数对的匹配问题，并通过哈希表在前缀中快速查找。