Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 148 A問題 mod M

AtCoder ARC148 ARC A問題 300 pts

問題

提出解答

問題の概要

長さ $N$ の非負整数列 $A=(A_1, \dots, A_N)$ が与えられる. 次のようにして長さ $N$ の非負整数列 $B$ を作成する.

$B=(A_1 \pmod{M}, \dots, A_N \pmod{N})$

$M$ をうまく選び, $B$ に出てくる整数の種類の数の最小値を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$0 \leq A_i \lt 10^9$

解法

まず, $M=2$ とすると $B$ の各項が $0$ or $1$ になり, 種類の数が高々 $2$ になる. よって, 正解は $2$ 以下であることがわかった.

よって, $B$ の各項が全て等しくなるような $M$ が存在するかどうかを判定する.

$A$ の各項が全て等しいときは任意の $2$ 以上の整数で $B$ の各項が等しくなる.

以降は $A$ に現れる整数の種類の数は $2$ 以上とする.

以下が成立する.

整数 $x,y$ と正の整数 $m$ に対して, 以下は同値である.

$x$ を $m$ で割った余りと $y$ を $m$ で割った余りは等しい
$m$ は $x-y$ の約数である.

よって, 上のことを利用することにより, 次のように変形できる.

$B_1=\dots=B_N$ となる $2$ 以上の整数 $M$ が存在する.
以下を満たすような以上の整数が存在する.
- 任意の $i=1,2, \dots, N-1$ に対して, $M$ は $A_{i+1}-A_i$ の約数である.

このとき, 「 $A$ に現れる整数の種類の数は $2$ 以上」という仮定から, $A_{i+1}-A_i \neq 0$ となる $i$ が存在する. よって,

$\displaystyle g:=\gcd_{i=1,2, \dots, N-1} \left(A_{i+1}-A_i \right)$

とすると, $g \gt 0$ である.

この $g$ によって, 以下は同値になる.

以下を満たすような以上の整数が存在する.
- 任意の $i=1,2, \dots, N-1$ に対して, $M$ は $A_{i+1}-A_i$ の約数である.
$g \geq 2$

そして, $A$ の各項が全て等しいとき, その時に限り $g=0$ である.

これらによって, 解答は

$g \neq 1$ ならば $1$ ( $g \gt 1$ のときは $M=g$ のとき, $g=0$ のときは任意の $2$ 以上の整数 $M$ )
$g=1$ ならば $2$ ( $M=2$ のとき)

である.