分数: 800 点
问题陈述
让我们来看看 P = 200\,003。 你被给予 N 整数 A_1, A_2, \ldots, A_N。 求总和 ((A_i \cdot A_j) \bmod P) 总的来说 N \cdot (N-1) / 2 无序元素对 (i < j).
请注意,总和不是以模数计算的 P.
约束
- 2 \leq N \leq 200\,000
- 0 \leq A_i < P = 200\,003
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出。
N A_1 A_2 \cdots A_N
输出
打印一个整数 — 总和 ((A_i \cdot A_j) \bmod P).
示例输入 1
4 2019 0 2020 200002
示例输出 1
474287
非零乘积是:
- 2019 \cdot 2020 \bmod P = 78320
- 2019 \cdot 200002 \bmod P = 197984
- 2020 \cdot 200002 \bmod P = 197983
所以答案是 0 + 78320 + 197984 + 0 + 0 + 197983 = 474287.
示例输入 2
5 1 1 2 2 100000
示例输出 2
600013