AtCoder Beginner Contest 186 E問題 Throne 自習Tips

原典

問題はこちら
公式解説はこちら

記事の動機

ざっくり問題を説明すると、円周上に並べた座席を移動して決まった座席（問題上は玉座(Throne)）に戻れるか
という設定で、個人的に、公式解説の1行目の式にはすぐ気づいたものの、

Ax \equiv B \bmod{M} \text{となる最小の}x\text{を求めよ。}

の解法と逆元の存在がわからなかったので一部解答を鵜呑みにしつつ、納得のために検索した結果のまとめ。

解説からの個人的理解

整数$l, m, n$に対し、$\gcd(l, m)$は$l, m$の最大公約数を、$\gcd(l, m, n)$は$l, m, n$の最大公約数を表すものとすると、

\exists x \in \mathbb{Z}, x\gt0 \ s.t. \  Ax \equiv B \bmod{M} \\

\Leftrightarrow \exists x,y \in \mathbb{Z}, x\gt0 \ s.t. Ax+My=B \\

d=\gcd(A, B, M)\text{とすると，}A=A'd, B=B'd, M=M'd\text{と書けるので、} \\

\begin{equation}

\Leftrightarrow \exists x,y \in \mathbb{Z}, x\gt0 \ s.t. A'x+M'y=B' 

\end{equation}

ここで、ベズーの等式¹（ベズーの補題ともいうらしい）を$A', M'\neq0, A', M' \in \mathbb{Z}$であることに注意して適応すると、

\exists x', y' \in \mathbb{Z} \ s.t. \ A'x'+M'y'=\gcd(A', M')

が従う。一旦この主張を認めて、$A'$と$M'$が互いに素（$\gcd(A', M')=1$）ならば、

A'x'+M'y'=1 \tag{A} \\
\therefore A'x' \equiv 1 \bmod{M}

で、$x'$は法$M$における$A'$の剰余の逆元ということがわかる。また、式$(\text{A})$の両辺に$B'$を乗じて

A'(B'x')+M'(B'y')=B'

として$x(=B'x')$を求められる。

個人的納得のための脱線

上の記述の中に出てくるベズーの等式については、主張を改めて書くことや証明はWikipediaの該当ページ¹に任せてこの記事では割愛。（記事には更に引用元となる書籍が記されて信用できそうであり、記事記載の証明は内容を追いかけての納得はできる）

更に個人的に引っかかったポイントとして、公式解説では（文脈による文字の差はあるが）$\gcd(A', M')\neq1$ならば解なしと書かれていた点。
これについては、剰余の逆元について調べていたページ²で、

「割る数」と「法」が互いに素であるという条件は、
合同式の除算が可能になるだけではなくて、乗算の逆元の存在を示す十分条件

とも書かれており、これがわからず、証明を探してみた。³

命題として以下の同値性の証明を見つけたので一旦納得。

\begin{align}
&m,n \gt 0, m,n \in \mathbb{Z} \\
&\gcd(m,n)=1 \tag{1} \\
\Leftrightarrow& \ \exists x,y \in \mathbb{Z} \ s.t. \ mx+ny=1 \tag{2} \\
\Leftrightarrow& \ \exists x \ s.t. mx \equiv 1 \bmod{n} \tag{3} \\
\Leftrightarrow& \ \exists x \ s.t. nx \equiv 1 \bmod{m} \tag{4} \\
\end{align}

証明については、参考元を踏襲して略記をすると
$(1) \Rightarrow (2)$ ベズーの等式の$m,n$が互いに素なとき
$(2) \Rightarrow (1)$ $1=mx+ny=\gcd(m,n)(\frac{m}{\gcd(m,n)}x+\frac{n}{\gcd(m,n)}y)$と、$\gcd(m,n)$は1を割り切るので$\gcd(m,n)=1$
$(2) \Rightarrow (3)$ $mx+ny=1$の各項に$\bmod{n}$をとる
$(3) \Rightarrow (2)$ $\exists x \in \mathbb{Z} \ s.t. \ mx \equiv 1 \bmod{n} \Rightarrow \exists q \in \mathbb{Z} \ s.t. \ mx=1+nq \therefore y=(-q)$として$mx+n(-q)=1$

$(2) \Rightarrow (4)$、$(4) \Rightarrow (2)$は$(2) \Rightarrow (3)$、$(3) \Rightarrow (2)$と同様の手法

参考にした原本ページリンク

剰余の乗法の逆元の丁寧と感じた説明
https://tex2e.github.io/blog/crypto/invmod

ブログ 晴耕雨読 内でpythonでのモジュラ逆数を出す実装が載っていたページ
https://tex2e.github.io/blog/crypto/modular-mul-inverse

剰余の乗法の逆元はモジュラ逆数として記事があった
https://ja.wikipedia.org/wiki/モジュラ逆数

個人メモだが、素数と互いに素な数の場合、剰余の逆元で出てくるフェルマーの小定理
https://ja.wikipedia.org/wiki/フェルマーの小定理

(余談)一通り調べたあとで

https://qiita.com/keigo0205/items/bd811a599bc006eb6ab3
pythonの3.8系から組み込み関数のpowが拡張して、
逆元を求められるようになっていると知って驚いた。
あまりアルゴリズムがわからなくても少しは取り組める問題があるかも？←頼っていいのか

ローカル環境アップデートして過去問練習しよう。。

1. ベズーの等式 https://ja.wikipedia.org/wiki/ベズーの等式
   ベズーの等式
   https://ja.wikipedia.org/wiki/ベズーの等式 ↩ ↩²

2. 剰余の乗法の逆元の丁寧と感じた説明 https://tex2e.github.io/blog/crypto/invmod ↩

3. 乗算の逆元が存在することの必要十分条件性の証明 http://www2.kobe-u.ac.jp/~kikyo/Sites/lec/16/mathA/code.pdf
   乗算の逆元が存在することの必要十分条件性の証明
   http://www2.kobe-u.ac.jp/~kikyo/Sites/lec/16/mathA/code.pdf ↩