← 返回题目列表

AtCoder · agc047_c

C. 乘积模

中文机器翻译题面 查看原题

分数: 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