CodeIQ MAGAZINECodeIQ MAGAZINE

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

2017.09.14 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 12
  • このエントリーをはてなブックマークに追加
riverplus

「数学の問題をプログラミングで解こう!」シリーズ。
nの階乗を割り算したときの余りについての問題でした。
nが巨大ですので、うまくパターンを見つけて計算量を下げましょう。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックしてください!
by CodeIQ運営事務局

問題のおさらい

自然数 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 を、それぞれ np で置き換えてみます。これはさほど難しくないと思います。上の図と見比べてください。下図のようになります。

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

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

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

実装

最後に、これをコーディングしていきましょう。再帰が書きやすいです。関数 F(n, p) で、始めに np の大小をチェックして、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さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 12
  • このエントリーをはてなブックマークに追加

■関連記事

【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...
【息抜き】ファイル名を作ろう【言語不問】解答と解説... 【息抜き】ファイル名を作ろう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 ファイルをディレクトリ内に作成する際、同じ名前のファイルがあると、末尾に数字を付けるなどして同じ名前にならないようにします。 こうし...
【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
【夏のミステリー】時間制限の密室 解答と解説... 【夏のミステリー】時間制限の密室 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 (なんやかんやあって)命からがら逃げてきた、あなた。 しかし逃げ込んだ部屋にあなたが入った途端、自動でドアはロックされ、しかも10分後にはガ...
数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説... 問題のおさらい n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。 積む際には次のルールに従います。 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。 全ての丸太は一...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ