問題一覧 > 通常問題

No.1972 Modulo Set

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 128
作問者 : magstamagsta / テスター : 👑 KazunKazun
6 ProblemId : 6830 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-06 21:59:20

問題文

$N$ 個の正整数 $A_1,A_2,...,A_N$ と 正整数 $M$ が与えられます。

$A_1,A_2...,A_N$ を要素とする集合を集合 $S$ とします。


$S$ の部分集合かつ以下の条件を満たす集合のうち、要素数が最大である集合の要素数を求めてください。

条件

集合の要素のうち異なる 2 つの数を取り出し、これらをそれぞれ $P, Q$ とする。

このとき、どのように数を取り出したとしても、$P+Q$ が $M$ の倍数となることはない。

(集合の要素数が $1$ の場合は、必ずこの条件を満たすとする。)

制約

  • $\displaystyle 1 \leq N \leq 10^5$
  • $\displaystyle 1 \leq M \leq 10^{12}$
  • $\displaystyle 1 \leq A_i \leq 10^{12} \ (1 \leq i \leq N)$
  • $\displaystyle A_i \neq A_j \ (1 \leq i,j \leq N, \ i \neq j)$
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N \ \ M$
$A_1 \ \ A_2 \ \dots \ A_N$

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
4 5
7 14 3 5
出力
3

$\{7, 14, 5\}$ や $\{14, 3, 5\}$ は、集合 $S$ の部分集合かつ条件を満たす集合です。

$\{7, 14, 3, 5\}$ は条件を満たさないため、最大の要素数は $3$ となります。

サンプル2
入力
1 8
3
出力
1

要素数が $1$ の場合、必ず条件を満たします。

サンプル3
入力
14 5
218 64 142 792 323 402 594 857 394 977 577 495 264 29
出力
12

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。