つい最近AtCorderに参加しました。
アルゴリズムは好きだけど今まで真面目に勉強はしていなかったのでこれを機にしっかりとまとめていこうと思います。
とりあえず最初の記事としては個人的に面白かった＆すごく簡単な問題についてアルゴリズムの組み立てと説明をしてみます。
問題は以下を参照してください。
B: 直方体 - AtCoder Beginner Contest 041 | AtCoder
この問題のキモは以下の２点
1. A * B まではlong(64ビット整数)で表せるけど A * B * Cは桁あふれしてしまう。
2. わる数である10^9+7が素数
割る数が素数なので、わる数を分解して複数回の式にしてしまうこともできません。なのでなんとか64bitの範囲内で収まる式に変形しないといけないというのがこの問いで求められてる課題なのだと思います。
ということで、A * B * C % 10^9+7をなんとか64bitで計算できる方法がないか考えてみます。
まず、 A * Bまでは64bit内に収まるので、ここで一旦区切って考えます。
ので、この値をXと定義します。
\begin{align} X = A \times B \label{1} \end{align}
今回の問題では 10^9+7で割った余りのみを求められているので、上記の式を10^9で割ったときの商とあまりに分解してみます。式が長くならないように
\begin{align} D = 10^9+7 \label{2} \end{align}
とすると、
\begin{align} X=aD+restX \label{3} \end{align}
となります。
は
を10^9+7で割ったときの商で、
はそのときの余りです。
そしたら、\eqref{3} をA * B * Cの式に代入してみると \eqref{1} より
\begin{align} (aD + restX) \times C \end{align}
となります。
ここで注目したいのはは10^9+7で割り切れる値（\eqref{2}より）なので、考えないといけないのは
\begin{align} restX \times C \end{align}
だけとなります。
さらには10^9+7で割った余りなので
\begin{align} restX \lt 10^9+7 \label{6} \end{align}
が成り立ちます。なので
\begin{align} restX \times C \lt 10^{20} \label{7} \end{align}
も成立して無事にlongで計算できる範囲に収まることがわかります。
以上の証明は「余剰の性質」というのだそうです。（http://abc041.contest.atcoder.jp/data/abc/041/editorial.pdf）
知らなかった。。。
この問題を素直に解くためにアルゴリズムを考えると、自然とこの「余剰の性質」思いつくところに問題の作り方がうまいなぁと感激しました。
