1857F.md (2160B)
1 Source: https://codeforces.com/problemset/problem/1857/F 2 3 F. Sum and Product 4 5 time limit per test 6 7 4 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 You have an array $a$ of length $n$. 22 23 Your task is to answer $q$ queries: given $x,y$, find the number of pairs $i$ and $j$ ($1 \le i \lt j \le n$) that both $a_i + a_j = x$ and $a_i \cdot a_j = y$. 24 25 That is, for the array $[1,3,2]$ and asking for $x=3,y=2$ the answer is $1$: 26 27 * $i=1$ and $j=2$ fail because $1 + 3 = 4$ and not $3,$ also $1 \cdot 3=3$ and not $2$; 28 * $i=1$ and $j=3$ satisfies both conditions; 29 * $i=2$ and $j=3$ fail because $3 + 2 = 5$ and not $3,$ also $3 \cdot 2=6$ and not $2$; 30 31 Input 32 33 The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases. 34 35 The second line of each test case contains one integer $n$ ($1 \le n \le 2\cdot 10^5$) — the length of the array $a$. 36 37 The third line of each test case contains $n$ integers $a_1,a_2,\dots,a_n$ ($1 \le |a_i| \le 10^9$) — array $a$. 38 39 The fourth line of each test case contains the integer $q$ ($1 \le q \le 2\cdot 10^5$) — the number of requests. 40 41 The next $q$ lines contain two numbers each $x$ and $y$ ($1 \le |x|\le 2\cdot 10^9,1\le |y|\le 10^{18}$) — request. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. This is also guaranteed for the sum of $q$ values. 44 45 Output 46 47 For each test case print a line with $q$ numbers — the answers to the queries. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 3 57 58 1 3 2 59 60 4 61 62 3 2 63 64 5 6 65 66 3 1 67 68 5 5 69 70 4 71 72 1 1 1 1 73 74 1 75 76 2 1 77 78 6 79 80 1 4 -2 3 3 3 81 82 3 83 84 2 -8 85 86 -1 -2 87 88 7 12 89 ``` 90 91 Output 92 93 ``` 94 1 1 0 0 95 6 96 1 1 3 97 ``` 98 99 Note 100 101 For the first test case, let's analyze each pair of numbers separately: 102 103 * pair $(a_1,a_2)$: $a_1 + a_2 = 4$, $a_1 \cdot a_2 = 3$ 104 * pair $(a_1,a_3)$: $a_1 + a_3 = 3$, $a_1 \cdot a_3 = 2$ 105 * pair $(a_2,a_3)$: $a_2 + a_3 = 5$, $a_2 \cdot a_3 = 6$ 106 107 From this, we can see that for the first query, the pair $(a_1,a_3)$ is suitable, for the second query, it is $(a_2,a_3)$, and there are no suitable pairs for the third and fourth queries. 108 109 In the second test case, all combinations of pairs are suitable.