시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 16 | 11 | 7 | 58.333% |
Is it a programming contest?
You are given a prime number \(p\) and two subsets \(S\) and \(V\) of residues from \(0\) to \(p − 1\).
Your task is to find the number of pairs \((a, b)\) that satisfy the following set of equations:
All operations are performed modulo \(p\). Note that, when \(a \ne b\), the pairs \((a, b)\) and \((b, a)\) are considered different.
Division by zero is not allowed: when any of the two denominators turns into a zero, the congruence is considered false.
The first line contains a single integer \(p\) (\(2 \le p \le 10^6\), \(p\) is prime).
The second line contains a single integer \(n\): the size of \(S\) (\(0 \le n \le p\)).
The third line contains \(n\) distinct integers \(S_1, S_2, \dots , S_n\): the elements of \(S\) (\(0 \le S_i \le p − 1\)).
The fourth line contains a single integer \(m\): the size of \(V\) (\(0 \le m \le p\)).
The fifth line contains \(m\) distinct integers \(V_1, V_2, \dots , V_m\): the elements of \(V\) (\(0 \le V_i \le p − 1\)).
Print one integer: the number of solutions.
7 4 0 4 5 6 2 2 3
8
19 10 0 3 4 5 8 9 13 14 15 18 10 2 3 5 9 10 11 12 13 14 15
42