该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

B-相同余数对（remainder）

题目背景

在一次数论训练中，小 A 把一列整数都拿去对同一个正整数 $m$ 取模。

他发现，有些数虽然本身不同，但取模后的结果却一样。于是他想知道：在这列数中，一共有多少对数会得到相同的余数。

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$ ，以及一个正整数 $m$ 。

请你统计有多少对下标 $(i,j)$ 满足：

1 \le i < j \le n

且

a_i \bmod m = a_j \bmod m

输出满足条件的数对数量。

输入格式

第一行输入两个整数 $n,m$ ，分别表示序列长度和取模的模数。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ 。

输出格式

输出一个整数，表示满足条件的数对数量。

输入输出样例

输入 #1

6 4
1 5 7 9 10 14

输出 #1

样例解释

将每个数对 $4$ 取模之后，余数分别为： $\text{1 1 3 1 2 2}$

其中：

余数为 $1$ 的数有 $3$ 个，可以组成 $3$ 对；
余数为 $2$ 的数有 $2$ 个，可以组成 $1$ 对；
余数为 $3$ 的数有 $1$ 个，不能组成数对。

所以答案为：

3+1=4

数据范围

对于所有测试数据，保证：$1 \le n \le 2 \times 10^5,\quad 1 \le m \le 10^9,\quad 1 \le a_i \le 10^{18}$

本题共设 $20$ 个测试点，各测试点满足的限制如下：

测试点编号	分值	$n$	$m$	特殊性质
$\text{1}$	$5$	$\le 10$	$\le 10$	无特殊性质
$\text{2}$		$\le 10$	$=1$	$A$
$\text{3}$		$\le 20$		$B$
$\text{4}$		$\le 20$		$C$
$\text{5}$		$\le 100$	$\le 100$	无特殊性质
$\text{6}$		$\le 100$	$=2$	$D$
$\text{7}$		$\le 1000$		$E$
$\text{8}$		$\le 1000$		$F$
$\text{9}$		$\le 2000$		无特殊性质
$\text{10}$		$\le 5000$	$\le 10^5$	$B$
$\text{11}$		$\le 10^4$		无特殊性质
$\text{12}$		$\le 2 \times 10^4$		$G$
$\text{13}$		$\le 5 \times 10^4$	$\le 10^9$	无特殊性质
$\text{14}$		$\le 8 \times 10^4$		$E$
$\text{15}$		$\le 10^5$		$F$
$\text{16}$		$\le 1.2 \times 10^5$		$C$
$\text{17}$		$\le 1.5 \times 10^5$		无特殊性质
$\text{18}$		$\le 1.8 \times 10^5$		$G$
$\text{19}$		$\le 2 \times 10^5$		$A$ 或 $D$
$\text{20}$		$\le 2 \times 10^5$		无特殊性质

特殊性质 $A$ ：保证 $m=1$ 。

特殊性质 $B$ ：保证所有数对 $m$ 取模后的结果两两不同。

特殊性质 $C$ ：保证所有数对 $m$ 取模后的结果都相同。

特殊性质 $D$ ：保证 $m=2$ 。

特殊性质 $E$ ：保证 $a_i \le 10^9$ 。

特殊性质 $F$ ：保证序列已经按非递减顺序给出。

特殊性质 $G$ ：保证 $m \le 25$ 。

Overview

类型传统题

Time Limit 1000ms

Memory Limit 256MiB

Stats

题目

A B C D E

「果壳杯」 ROUND 44 (Div. 4)

未参加

状态: 已结束
规则: IOI
题目: 5
开始于: 2026-4-3 18:00
结束于: 2026-4-10 18:00
持续时间: 2 小时
主持人: _Separation
参赛人数: 17