Kazun の競プロ記録

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

AtCoder Regular Contest 149 A問題 Repdigit Number

AtCoder ARC149 ARC A問題 300 pts

問題

提出解答

問題の概要

以下の条件を全て満たす正の整数 $X$ は存在するか? 存在するならば, そのような整数の最大値を求めよ.

(1) $0 \lt X \lt 10^N$ で, $X$ の $10$ 進表記はどの桁の数字も等しい.
(2) $X$ は $M$ の倍数

制約

$1 \leq N \leq 10^5$
$1 \leq M \leq 10^9$

解法

まず, 条件 (1) を満たす整数の数は, 桁数とどの数字を並べるかを考えることによって, 実は $9N$ 個であり, $N \leq 10^5$ の制約から, 高々 $10^6$ 個である. よって, この $9N$ 個の整数を $M$ で割った余りを高速に計算できれば全列挙で求められそうである.

$1$ 以上 $9$ 以下の整数 $X$ と $1$ 以上 $N$ 以下の整数 $D$ に対して, $X$ を $D$ 個並べた整数を $T(X,D)$ と書くことにすると,

$T(X,1)=X$
$T(X,D)=10T(X,D-1)+D \quad (2 \leq D \leq N)$

が成り立つから, $T(X,D)$ を $M$ で割った余りは

$T(X,1) \pmod{M}=X \pmod{M}$
$T(X,D) \pmod{M}= (10T(X,D-1)+D) \pmod{M} \quad (2 \leq D \leq N)$

で求められることができる.

また, $T(X,D)$ と $T(Y,E)$ の整数における大小関係は整数の組 $(D,X)$ と $(E,Y)$ の辞書式順序と一致する.

以上のことから, $X=1,2, \dots, 9$ それぞれについて, $D=1,2, \dots, N$ の順に $T(X,D) \pmod{M}$ を上で求めた漸化式で求め, $M$ の倍数となるような $(D,X)$ のうち, $(X,D)$ が最大となるような整数の組を $(X', D')$ としたとき, 正解は $T(X', D')$ である.

計算量は $O(9 \times N)=O(N)$ 時間である.