Kazun の競プロ記録

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

AtCoder Regular Contest 131 A 問題 Two Lucky Numbers

AtCoder ARC ARC131 A問題 300 pts

問題

提出解答

問題の概要

$A,B$ に対して, 以下の条件を全て満たす正の整数 $X$ を1つ見つけよ.

$X$ の十進表記を文字列とみなすと, 連続する部分文字列に $A$ が存在する.
$2X$ の十進表記を文字列とみなすと, 連続する部分文字列に $B$ が存在する.
$X \lt 10^{18}$

制約

$1 \leq A,B \lt 10^8$

解法

$X=(5 \times 10^8)B+A$ とすれば条件を満たす. 以下は証明である.

$A \lt 10^8$ より, $X$ を $10^8$ で割った余りは $A$ である. よって, $X$ の右から高々 $8$ 文字が $A$ と一致する.
$2X=10^9 B+2A$ であり, $2A \lt 10^9$ より, $2X$ の下 $8$ 桁を除くと, $B$ となる.
$X=(5 \times 10^8)B+A \lt (5 \times 10^8+1) \times 10^8 \lt 6 \times 10^{16} \lt 10^{18}$ である.

よって, 条件を満たすような $X$ を見つけ出すことができた.