codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1931D.md (1847B)


      1 Source: https://codeforces.com/problemset/problem/1931/D
      2 
      3 D. Divisible Pairs
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Polycarp has two favorite integers $x$ and $y$ (they can be equal), and he has found an array $a$ of length $n$.
     22 
     23 Polycarp considers a pair of indices $\langle i, j \rangle$ ($1 \le i \lt j \le n$) beautiful if:
     24 
     25 * $a_i + a_j$ is divisible by $x$;
     26 * $a_i - a_j$ is divisible by $y$.
     27 
     28 For example, if $x=5$, $y=2$, $n=6$, $a=$[$1, 2, 7, 4, 9, 6$], then the only beautiful pairs are:
     29 
     30 * $\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$);
     31 * $\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$).
     32 
     33 Find the number of beautiful pairs in the array $a$.
     34 
     35 Input
     36 
     37 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.
     38 
     39 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.
     40 
     41 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.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output a single integer — the number of beautiful pairs in the array $a$.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 7
     55 
     56 6 5 2
     57 
     58 1 2 7 4 9 6
     59 
     60 7 9 5
     61 
     62 1 10 15 3 8 12 15
     63 
     64 9 4 10
     65 
     66 14 10 2 2 11 11 13 5 6
     67 
     68 9 5 6
     69 
     70 10 7 6 7 9 7 7 10 10
     71 
     72 9 6 2
     73 
     74 4 9 7 1 2 2 13 3 15
     75 
     76 9 2 3
     77 
     78 14 6 1 15 12 15 8 2 15
     79 
     80 10 5 7
     81 
     82 13 3 3 2 12 11 3 7 13 14
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 2
     89 0
     90 1
     91 3
     92 5
     93 7
     94 0
     95 ```