数学的な知見がいっぱいあったので備忘録です。
問題概要
日本語なので原文を参照してください → D: チップ・ストーリー ~黄金編~ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder
解説
この問題を解くには、いくつかの数学知識が必要です。
桁和と剰余の関係
唐突ですが、桁和と剰余には以下のような関係があります。
- 非負整数
を
進数で表した際の桁和が
であるとする。このとき、
が成り立つ。
なぜこのようになるか見ていきましょう。以下、 は
桁であるとし、
の
桁目を
と表現することにします。
まず、条件より以下の 2 つの式が成立します。
式 1 から式 2 を引いてみます。さらに、等式の両辺を整数 で割ったあまりは当然等しいので、
を法として考えます。すると、以下のようになります。
ここで、以下の性質を用います。
つまり、 から
減じたものは
を法として
と合同であるという主張です。これは
であることから
が分かり、あとは移項すればさきほど示した式になります。
この性質を使うと、 であることが言えるので、最初に示したかった
が示せました!
中国剰余定理
さて、もとの問題では 「 進数で表現した時の桁和」が入力として与えられていたので、これを利用して「求めたい整数
を
で割った余り」が何であるかは求めることができます。しかし、実際に知りたいのは「整数
が何であるか」です。これはどのようにして求められるでしょうか?
実はこの問題の場合はヒントが多いので、例えば 2, 3, 5, 7, 11, 13, 17, 19 で割った余りが一致する数 を全探索で探し、更に
を全探索しても正解することができるようです。今回はこのような全探索の解法ではなく、色々と使える数学の道具である中国剰余定理を紹介します。
を、どの 2 つの
を取っても互いに素であるような整数とする。このとき、任意の
に対して、
を満たす整数
が、
を法として一意に存在する。つまり、
の範囲に条件を満たす
が一つだけ存在する。
本記事では紹介だけにとどめます。証明については [1] [2] を参考にしてください。この定理を利用すると、進数 が素数であるものに関して中国剰余定理を適用し、条件を満たしているかチェックすることで解くことができます。
参考になるページ
定理そのものの証明に役立つページです。中国剰余定理を証明するときにベズーの等式が必要になるので、そちらの証明は [2] を参考にしてください。
[1] 中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語
[2] 一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語
中国剰余定理を解くアルゴリズムが紹介されているページです。
[3] 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita