C. Whole Product of Pairwise Distances

Whole Product of Pairwise Distances

AtCoder

⌀ 1714

Whole Product of Pairwise DistancesAI (CI翻译)

Problem Statement

You are given a sequence $A$ of $N$ positive integers. Find the remainder when $\prod_{1 \leq i < j \leq N}|A_i-A_j|$ is divided by $N$ .

Solve $T$ test cases per input.

Constraints

$1 \leq T \leq 10^5$
$2 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$
The sum of $N$ over all test cases is at most $2 \times 10^5$ .
All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case $\mathrm{case}_t$ is given in the following format:

N
A_1 A_2 \ldots A_N

Output

Output the answers over a total of $T$ lines. The $t$ -th line should contain the answer for the $t$ -th test case.

{"titleZh":"两两距离的乘积","bodyZh":"## 题目描述\n\n给定一个由 $N$ 个正整数组成的序列 $A$ 。\n求 $\prod_{1 \\leq i < j \\leq N}|A_i-A_j|$ 除以 $N$ 的余数。\n\n每组输入中有 $T$ 组测试数据，请分别求解。\n\n## 约束条件\n\n- $1 \\leq T \\leq 10^5$ \n- $2 \\leq N \\leq 2 \\times 10^5$ \n- $1 \\leq A_i \\leq 10^9$ \n- 所有测试数据的 $N$ 之和不超过 $2 \\times 10^5$ 。\n- 输入的所有值均为整数。\n\n## 输入格式\n\n输入从标准输入按以下格式给出：\n\n\nT\n\\mathrm{case}_1\n\\mathrm{case}_2\n\\vdots\n\\mathrm{case}_T\n`\n\n每组测试数据 $\\mathrm{case}_t$ 的格式如下：\n\n`\nN\nA_1 A_2 \\ldots A_N\n\n\n## 输出格式\n\n共输出 $T$ 行答案。第 $t$ 行应包含第 $t$ 组测试数据的答案。"}AI (CI翻译)

样例

Input #1

3
3
1 9 5
3
2 2 3
5
11 33 22 55 44

Output #1

2
0
3

For the first test case, $|A_1-A_2| \times |A_1-A_3| \times |A_2-A_3|=8 \times 4 \times 4=128$, and the remainder when this is divided by $3$ is $2$.

题目信息

题号

arc223_c

所属比赛

AtCoder Regular Contest 223

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。