「ディバイド・アウト」問題解答 ( CodeIQ )

CodeIQ 数学

CodeIQというところでプログラミング問題「ディバイド・アウト」に解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 空白区切りで入力される自然数 $n,p\,(1\le n\le 10^{12},\, 1\le p\le 10^5)$ に対し、$F(n,p)$の値を出力する
  • $F(n,p)$とは $n!$を割り切れる限り$p$で割り、更にそれを$p$で割った時の剰余を表す。

例えば、$(n,p)=(12,5)$の場合、12!は5で2回割ることができ、$12!\div 5^2=19160064\equiv 4\,\,mod\,5$ であるため、$F(12,5)=4$と分かります。

解説

規則性の整理

まずは規則性を明らかにします。

上で挙げた例を少し変えて$F(13,5)$の場合ですが、13! を次のように整理してみます。 $$ \begin{eqnarray} &\,&13! \\ &=&1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13 \\ &=&(1\cdot 2\cdot 3\cdot 4)\cdot(6\cdot 7\cdot 8\cdot 9)\cdot(11\cdot 12\cdot 13)\cdot(5\cdot 10) \\ &=&(1\cdot 2\cdot 3\cdot 4)\cdot(6\cdot 7\cdot 8\cdot 9)\cdot(11\cdot 12\cdot 13)\cdot 5^2\cdot(1\cdot 2) \\ \end{eqnarray} $$

つまり、$p=5$の倍数かどうかで分けて見たことになります。

最終的には ( 割れるだけ割ってから更に ) $p=5$で割った余りを計算するため、1～4の積を6～9も同じと見做すようなことが、つまり $6\cdot 7\cdot 8\cdot 9\equiv 1\cdot 2\cdot 3\cdot 4$ や $11\cdot 12\cdot 13\equiv 1\cdot 2\cdot 3$ とすることができます。つまり、 $$ \begin{eqnarray} &\,&13!=(1\cdot 2\cdot 3\cdot 4)\cdot(6\cdot 7\cdot 8\cdot 9)\cdot(11\cdot 12\cdot 13)\cdot 5^2\cdot(1\cdot 2) \\ &\Leftrightarrow& \frac{13!}{5^2}\equiv (1\cdot 2\cdot 3\cdot 4)\cdot(6\cdot 7\cdot 8\cdot 9)\cdot(11\cdot 12\cdot 13) \cdot(1\cdot 2)\,\,mod\,5 \\ &\Leftrightarrow& \frac{13!}{5^2}\equiv (1\cdot 2\cdot 3\cdot 4)\cdot(1\cdot 2\cdot 3\cdot 4)\cdot(1\cdot 2\cdot 3) \cdot(1\cdot 2)\,\,mod\,5 \\ \end{eqnarray} $$

$F$での形は次の通りです。

  • $F(13,5)\equiv F(4,5)^2 \cdot F(3,5) \cdot F(2,5)$

これを一般の$n,p$で書くと次のようになります。なお、$0!=1$ですから$F(0,p)=1$であり、$n$が$p$の倍数でも不整合はありません。

  • $F(n,p)\equiv F(p-1,p)^{\lfloor n/p \rfloor} \cdot F(n\,mod\,p,p) \cdot F(\lfloor n/p \rfloor,p)\,\,mod\, p$

これを再帰的に繰り返していけば、それぞれ$p$未満の階乗の剰余の計算に落とすことができます。例えば、$F(1000,17)$であれば、$1000\div 17=58\cdots 14,~58\div 17=3\cdots 7$ と順に商・余りが出ますから、次のように計算できます。

$$ \begin{eqnarray} &\,&F(1000,17) \\ &=&F(16,17)^{58} \cdot F(14,17) \cdot F(58,17) \\ &=&F(16,17)^{58} \cdot F(14,17) \cdot ( F(16,17)^3 \cdot F(7,17) \cdot F(3,7) ) \\ \end{eqnarray} $$

ウィルソンの定理

ということで、この関係式が分かった時点で実装を進めるには十分なのですが。

  • $F(0,p)=1$
  • $F(n,p)\equiv F(p-1,p)^{\lfloor n/p \rfloor} \cdot F(n\,mod\,p,p) \cdot F(\lfloor n/p \rfloor,p)\,\,mod\, p$

べき乗の出てくる$F(p-1,p)\equiv(p-1)!\,\,mod\,p$ のところを更に簡略化する方法があります。それが次の式で表されるウィルソンの定理です。

  • $(p-1)!\equiv -1\,\,mod\,p$

この証明については、ウィルソンの定理とその２通りの証明 | 高校数学の美しい物語などをご覧ください。

これを利用すると、次のようになります。

  • $F(n,p)\equiv (-1)^{\lfloor n/p \rfloor} \cdot F(n\,mod\,p,p) \cdot F(\lfloor n/p \rfloor,p)\,\,mod\, p$

べき乗の部分は、指数の偶奇で符号が反転するだけなので、更に計算が楽になっています。

実装

さて、実装にあたっては上に上げた再帰を意識した訳なのですが、余り深く考えていなかった-1のべき乗を作るのに心理的な抵抗があったため、少しヒネリを加えました。

元の$F(n,p)$に類似した「$-1$～$-n$の積を$p$でできるだけ割り、それを$p$で割った余り」を$F_-(n,p)$とするのです。

要は、$F_-(n,p)\equiv (-1)^nF(n,p)\Leftrightarrow F(n,p)=(-1)^nF_-(n,p)$ ということなのですが、これも全く同じ議論により、

  • $F_-(n,p)\equiv (-1)^{\lfloor n/p \rfloor} \cdot F_-(n\,mod\,p,p) \cdot F_-(\lfloor n/p \rfloor,p)\,\,mod\, p$

であることが分かります。

そうすると、-1のべき乗の部分は$F$あるいは$F_-$に吸収させて、

  • $F(n,p)\equiv F(n\,mod\,p,p)\cdot F_-(\lfloor n/p \rfloor,p)\,\,mod\,p$
  • $F_-(n,p)\equiv F_-(n\,mod\,p,p)\cdot F(\lfloor n/p \rfloor,p)\,\,mod\,p$

というように、$F,\,F_-$を交互に繰り返すような漸化式に置き換えることができます。この違いを第2引数yで表現した再帰関数fを実装したのが、以下の提出版Ruby(89)です。

終わりに

高速化についてはさっぱり吟味してなかったのですが、次のような情報が…

上で整理した考えでは、せいぜい$O(p+log(n))$位までしかできなくて、それよりもずっと速いのですが、さっぱり何やってるのか分からないのが…。

ともあれ、色々な方のコードが CodeIQ「ディバイド・アウト」問題 みんなのコード - Togetterまとめ にまとめられていますので、一度ご覧になってはいかがでしょうか。