codeforces-scrape

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

1248A.md (2252B)


      1 Source: https://codeforces.com/problemset/problem/1248/A
      2 
      3 A. Integer Points
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 DLS and JLS are bored with a Math lesson. In order to entertain themselves, DLS took a sheet of paper and drew $n$ distinct lines, given by equations $y = x + p_i$ for some distinct $p_1, p_2, \ldots, p_n$.
     22 
     23 Then JLS drew on the same paper sheet $m$ distinct lines given by equations $y = -x + q_i$ for some distinct $q_1, q_2, \ldots, q_m$.
     24 
     25 DLS and JLS are interested in counting how many line pairs have integer intersection points, i.e. points with both coordinates that are integers. Unfortunately, the lesson will end up soon, so DLS and JLS are asking for your help.
     26 
     27 Input
     28 
     29 The first line contains one integer $t$ ($1 \le t \le 1000$), the number of test cases in the input. Then follow the test case descriptions.
     30 
     31 The first line of a test case contains an integer $n$ ($1 \le n \le 10^5$), the number of lines drawn by DLS.
     32 
     33 The second line of a test case contains $n$ distinct integers $p_i$ ($0 \le p_i \le 10^9$) describing the lines drawn by DLS. The integer $p_i$ describes a line given by the equation $y = x + p_i$.
     34 
     35 The third line of a test case contains an integer $m$ ($1 \le m \le 10^5$), the number of lines drawn by JLS.
     36 
     37 The fourth line of a test case contains $m$ distinct integers $q_i$ ($0 \le q_i \le 10^9$) describing the lines drawn by JLS. The integer $q_i$ describes a line given by the equation $y = -x + q_i$.
     38 
     39 The sum of the values of $n$ over all test cases in the input does not exceed $10^5$. Similarly, the sum of the values of $m$ over all test cases in the input does not exceed $10^5$.
     40 
     41 In hacks it is allowed to use only one test case in the input, so $t=1$ should be satisfied.
     42 
     43 Output
     44 
     45 For each test case in the input print a single integer — the number of line pairs with integer intersection points.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 3
     54 1 3 2
     55 2
     56 0 3
     57 1
     58 1
     59 1
     60 1
     61 1
     62 2
     63 1
     64 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 3
     71 1
     72 0
     73 ```
     74 
     75 Note
     76 
     77 The picture shows the lines from the first test case of the example. Black circles denote intersection points with integer coordinates.
     78 
     79  ![](https://espresso.codeforces.com/b9b5ce3ee370f82b94ed01d7804650d75b30d3b1.png)