4. 【Codeforces Round 925 (Div. 3)】D. Divisible Pairs

本文主要是介绍4. 【Codeforces Round 925 (Div. 3)】D. Divisible Pairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$D . 可除对$ $每次测试时限： 2 秒$ $每次测试的内存限制： 256 兆字节$

题目描述

波利卡普有两个最喜欢的整数 $x$ 和 $y$ （它们可以相等），他找到了一个长度为 $n$ 的数组 $a$ 。

如果出现以下情况，波利卡普认为一对索引 $\langle i, j \rangle$ ( $\le i < j \le n$ ) 很美：

$a_i + a_j$ 可以被 $x$ 整除；
$a_i - a_j$ 能被 $y$ 整除。

例如，如果 $x = 5$ , $y = 2$ , $n = 6$ , $a =$ [ $1, 2, 7, 4, 9, 6$ ]，那么唯一美丽的一对是：

$\langle 1, 5 \rangle$ : $a_1 + a_5 = 1 + 9 = 10$ $10$ 能被 $5$ 整除）和 $a_1 - a_5 = 1 - 9 = -8$ （ $- 8$ 能被 $5$ 整除）。 $- 8$ 能被 $2$ 整除）；
$\langle 4, 6 \rangle$ : $a_4 + a_6 = 4 + 6 = 10$ $10$ 能被 $5$ 整除）和 $a_4 - a_6 = 4 - 6 = -2$ （ $- 2$ 能被 $2$ 整除( $- 2$ 能被 $2$ 整除）。

求数组 $a$ 中优美对的个数。

输入

输入的第一行包含一个整数 $t$ ( $\le t \le 10^4$ ) - 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含三个整数 $n$ 、 $x$ 和 $y$ （ $\le n \le 2 \cdot 10^5$ 、 $\le x, y \le 10^9$ ）–数组的大小和波利卡普最喜欢的整数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $\le a_i \le 10^9$ ) - 数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $\cdot 10^5$ 。

输出

对于每个测试用例，输出一个整数–数组 $a$ 中的漂亮配对数。

解题关键：使用嵌套map

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
const int N = 200010;int a[N];int main()
{int t; cin>>t;while(t--){int n,x,y; scanf("%d%d%d", &n, &x, &y);LL ans=0;map<int,map<int,int>>mp;for(int i=1;i<=n;i++){scanf("%d", &a[i]);ans+=mp[a[i]%y][(x-a[i]%x)%x];mp[a[i]%y][a[i]%x]++;}printf("%lld\n",ans);}return 0;
}

一些注意事项：

①先更新ans再将当前枚举的数存入mp中去
②在更新ans的时候要+对值，即应该是ans+=mp[a[i]%y][(x-a[i]%x)%x]而不是ans+=mp[a[i]%y][x-a[i]%x]
③这道题中的mp必须使用map类型而不能是unordered_map类型。相比之下，unordered_map哈希表的插入、查找和删除操作的平均时间复杂度是 O(1)，但在最坏情况下的时间复杂度可能会达到 O(n)，这取决于哈希函数的质量和哈希冲突的情况。而map(红黑树)则保证了更稳定的性能，不会受到哈希冲突的影响。