ガジェット通信 GetNews

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説

DATE:
  • ガジェット通信 GetNewsを≫

問題のおさらい

自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、その商をさらに p で割ったときの余りを F(n, p) と定義します。

例えば F(12, 5)=4 です。
12!(=479001600)は 5 で最大 2 回割ることができます。その商は 19160064 です。
さらにこれを 5 で割った余りは 4 です。

同様に、F(5, 3)=1, F(20, 7)=5, F(1000, 31)=11 となることが確かめられます。

標準入力から、自然数 n と素数 p (1 ≦ n ≦ 1012, 1 ≦ p ≦ 105)が半角空白区切りで与えられます。
標準出力に F(n, p) の値を出力するプログラムを書いてください。

方針:問題のサイズを小さくしよう

n! の p での割り算に関する問題です。単純には、n! の値を実際に計算してみる方法が思いつきますが、今回は n の上限が 1012 とかなり大きいため、n! の値をメモリに収めることは到底できません。別の方法として、n! の値そのものを計算するのでなく、1×2×3×4× … と順に掛け算をしながら、都度 p で割り切った余りを計算するというやり方も考えられますが、やはり最大で 1012 回程度の計算が必要になるため、1 秒の制限時間で答えを出すことはできません。

そこで本問では、繰り返しのパターンに着目しましょう。

n=32,p=5 の場合を例に説明します。下図は 32! を書き下したものです。5 の倍数がポイントです。本問では 5 の倍数を 5 で割り尽くす必要があり、話がややこしくなります。そこでまずは、5 の倍数とそうでない数とに話を分けて考えましょう。5 の倍数にはさまれた数字を取り出し、カタマリに分けてみます。「1・2・3・4」や「6・7・8・9」「11・12・13・14」などです。下図のようになります。

数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説

さてここで、それぞれの赤囲みを 5 で割った余りは、実はすべて等しくなります。例えば「6・7・8・9」なら、6,7,8,9 をそれぞれの余りを先に求めても余りの計算結果は変わりません。「1・2・3・4」に等しいです。したがって、図の赤囲みはすべて同じ値 F(4, 5) です。赤囲みは全部で 6 個(=32÷5 の整数部分)あるので、F(4, 5)6 が赤全体の結果になります。

参考:合同式の意味とよく使う6つの性質(外部サイト)

他の部分も考えてみましょう。右の黄囲みには端数の部分「31・32」があります。上と同様、先に各数字を 5 で割りましょう。「1・2」、すなわち F(2, 5) と同じ値になります。この 2 というのは 32 を 5 で割った余りです。

残るは 5 の倍数の部分です。ここが本問のポイントです。取り出すと「5・10・15・20・25・30」です。各数字を 5 で一度ずつ割ると「1・2・3・4・5・6」となります。この部分、実は F(6, 5) にほかなりません。

以上をまとめると下図のようになります。問題のサイズが一回り小さくなりましたね。

数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説

数式で書くと次のようになります。

数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説

次に一般形を考えましょう。さて、以上の議論の 32 と 5 を、それぞれ n と p で置き換えてみます。これはさほど難しくないと思います。上の図と見比べてください。下図のようになります。

数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説

さて、ここで一つ興味深い定理を紹介しましょう。ウィルソンの定理です。赤の F(p-1, p) の部分ですが、実はこの部分は、定理を使うと、計算するまでもなくイコール p-1 となることが分かります。もちろん実際に (p-1)! mod p を求めるコードを書いても構わないのですが、この定理で式がずいぶんシンプルになりますね。

参考:ウィルソンの定理(Wikipedia)

一般形で式を書くと次のようになります。

数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説

実装

最後に、これをコーディングしていきましょう。再帰が書きやすいです。関数 F(n, p) で、始めに n と p の大小をチェックして、n の方が小さいときは、そのまま n! mod p を計算するというコードになっています。また p-1 のべき乗を求めるところでの一工夫として、p-1 というのは 2 乗して余りをとると 1 ですから、べき乗の指数が奇数のときだけ p-1 をかけるようにしています。コード例(Python)は以下です。

def naive(n, p):
a = 1
for k in range(1, n+1):
a *= k
while a % p == 0: a /= p
a %= p
return a

def f(n, p):
if n < p: return naive(n, p)
a = p – 1 if (n / p) % 2 == 1 else 1
return (a * f(n / p, p) * f(n % p, p)) % p

n, p = map(int, raw_input().split())
print f(n, p)

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックしてください。

CodeIQ「ディバイド・アウト」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。