Divisible Pairs

题面翻译

你有两个整数 $x,y$ 和一个长为 $n$ 的数组 $a$。

你需要求出有多少个正整数对 $(i,j)$ 满足：

• $1 \le i < j \le n$
• $a_i + a_j$ 可被 $x$ 整除
• $a_i - a_j$ 可被 $y$ 整除

$t$ 组数据，$1 \le t \le 10^4 ,1 \le n \le 2 \times 10^5,\sum n \le 2 \times 10^5,1 \le a_i,x,y \le 10^9$。

题目描述

Polycarp has two favorite integers $x$ and $y$ (they can be equal), and he has found an array $a$ of length $n$ .

Polycarp considers a pair of indices $\langle i, j \rangle$ ( $1 \le i < j \le n$ ) beautiful if:

• $a_i + a_j$ is divisible by $x$ ;
• $a_i - a_j$ is divisible by $y$ .

For example, if $x=5$ , $y=2$ , $n=6$ , $a=$ [ $1, 2, 7, 4, 9, 6$ ], then the only beautiful pairs are:

• $\langle 1, 5 \rangle$ : $a_1 + a_5 = 1 + 9 = 10$ ( $10$ is divisible by $5$ ) and $a_1 - a_5 = 1 - 9 = -8$ ( $-8$ is divisible by $2$ );
• $\langle 4, 6 \rangle$ : $a_4 + a_6 = 4 + 6 = 10$ ( $10$ is divisible by $5$ ) and $a_4 - a_6 = 4 - 6 = -2$ ( $-2$ is divisible by $2$ ).

Find the number of beautiful pairs in the array $a$ .

输入格式

The first line of the input contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains three integers $n$ , $x$ , and $y$ ( $2 \le n \le 2 \cdot 10^5$ , $1 \le x, y \le 10^9$ ) — the size of the array and Polycarp’s favorite integers.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

输出格式

For each test case, output a single integer — the number of beautiful pairs in the array $a$ .

样例 #1

样例输入 #1

7
6 5 2
1 2 7 4 9 6
7 9 5
1 10 15 3 8 12 15
9 4 10
14 10 2 2 11 11 13 5 6
9 5 6
10 7 6 7 9 7 7 10 10
9 6 2
4 9 7 1 2 2 13 3 15
9 2 3
14 6 1 15 12 15 8 2 15
10 5 7
13 3 3 2 12 11 3 7 13 14

样例输出 #1

2
0
1
3
5
7
0

(a+b)%m==0同于(a%m+b%m)%m,有些情况下a%m+b%m==m,如果m==2，a==4,b==6就不成立，所以要特判（如果a%m==0||b%m==0，另一个数也一定是0），如果a>0&&b>0,(a-b)%m同于a%m-b%m

const int N = 2e5 + 10;
int  a[N];
int b[N], c[N];
void solve()
{
    int n;
    cin >> n;
    int x, y;
    cin >> x >> y;
    int ans = 0;
    map<PII, int> p;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        int k = x - a[i] % x;
        if (x == k) k = 0;
        ans += p[{k, a[i] % y}];
        p[{a[i] % x, a[i] % y}]++;
    }
    cout << ans << '\n';
}