hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

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 つの式が成立します。

  1.  d_k m^{k} + d_{k-1} m^{k-1} + \cdots + d_0 m^{0} = N
  2.  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 が一つだけ存在する。

本記事では紹介だけにとどめます。証明については [1] [2] を参考にしてください。この定理を利用すると、進数  m素数であるものに関して中国剰余定理を適用し、条件を満たしているかチェックすることで解くことができます。

参考になるページ

定理そのものの証明に役立つページです。中国剰余定理を証明するときにベズーの等式が必要になるので、そちらの証明は [2] を参考にしてください。

[1] 中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語

[2] 一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語

中国剰余定理を解くアルゴリズムが紹介されているページです。

[3] 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

[4] Garner のアルゴリズムと多倍長整数演算 - kirika_compのブログ

[5] 任意modでの畳み込み演算をO(n log(n))で - math314のブログ