Tutorial — Coordinate Crossings

Giao điểm của hai đường thẳng $y = x + p_i$ và $y = -x + q_j$ có tọa độ $x = \frac{q_j - p_i}{2}$ và $y = \frac{q_j + p_i}{2}$. Hãy tìm điều kiện cần và đủ để cả $x$ và $y$ đều là các số nguyên.

Tọa độ $x$ và $y$ là số nguyên khi và chỉ khi $p_i$ và $q_j$ có cùng tính chẵn lẻ. Như vậy, một cặp hai số chẵn hoặc một cặp hai số lẻ sẽ tạo ra một giao điểm nguyên.

Đếm số lượng phần tử chẵn và lẻ trong tập $p$, tương tự cho tập $q$. Kết quả cần tìm là tổng của tích hai số lượng chẵn và tích hai số lượng lẻ.