DDCC 2019 予選 D: チップ・ストーリー～黄金編～

数学的な知見がいっぱいあったので備忘録です。

問題概要

日本語なので原文を参照してください → D: チップ・ストーリー～黄金編～ - DISCO presents ディスカバリーチャンネルコードコンテスト2019 予選 | AtCoder

解説

この問題を解くには、いくつかの数学知識が必要です。

桁和と剰余の関係

唐突ですが、桁和と剰余には以下のような関係があります。

非負整数 $N$ を $m$ 進数で表した際の桁和が $s$ であるとする。このとき、 $N \equiv s \pmod{m-1}$ が成り立つ。

なぜこのようになるか見ていきましょう。以下、 $N$ は $k+1$ 桁であるとし、 $N$ の $i$ 桁目を $d_i$ と表現することにします。

まず、条件より以下の 2 つの式が成立します。

$d_k m^{k} + d_{k-1} m^{k-1} + \cdots + d_0 m^{0} = N$
$d_k + d_{k-1} + \cdots + d_0 = s$

式 1 から式 2 を引いてみます。さらに、等式の両辺を整数 $p$ で割ったあまりは当然等しいので、 $(m-1)$ を法として考えます。すると、以下のようになります。

$d_k (m^{k} - 1) + d_{k-1} (m^{k-1} - 1) + \cdots + d_0 (m^{0} - 1) \equiv N - s \pmod{m - 1}$

ここで、以下の性質を用います。

$m^{x} - 1 \equiv 0 \pmod{m-1}$

つまり、 $m^{x}$ から $1$ 減じたものは $m-1$ を法として $0$ と合同であるという主張です。これは $m \equiv 1 \pmod{m-1}$ であることから $m^{x} \equiv 1^{x} \equiv 1 \pmod{m-1}$ が分かり、あとは移項すればさきほど示した式になります。

この性質を使うと、 $0 \equiv N - s \pmod{m-1}$ であることが言えるので、最初に示したかった $N \equiv s \pmod{m-1}$ が示せました！

中国剰余定理

さて、もとの問題では「 $m$ 進数で表現した時の桁和」が入力として与えられていたので、これを利用して「求めたい整数 $n$ を $(m-1)$ で割った余り」が何であるかは求めることができます。しかし、実際に知りたいのは「整数 $n$ が何であるか」です。これはどのようにして求められるでしょうか？

実はこの問題の場合はヒントが多いので、例えば 2, 3, 5, 7, 11, 13, 17, 19 で割った余りが一致する数 $x$ を全探索で探し、更に $x + 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 k$ を全探索しても正解することができるようです。今回はこのような全探索の解法ではなく、色々と使える数学の道具である中国剰余定理を紹介します。

$m_1, m_2, \ldots, m_k$ を、どの 2 つの $m_i, m_j (i \neq j)$ を取っても互いに素であるような整数とする。このとき、任意の $a_1, a_2, \ldots, a_k$ に対して、

$x \equiv a_1 \pmod {m_1}$

$x \equiv a_2 \pmod {m_2}$

$\vdots$

$x \equiv a_k \pmod {m_k}$

を満たす整数 $x$ が、 $m_1 m_2 \ldots m_k$ を法として一意に存在する。つまり、 $0 \leq x \lt m_1 m_2 \ldots m_k$ の範囲に条件を満たす $x$ が一つだけ存在する。