codeforces-scrape

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

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.