Problem 288

4月18日(土) 21時に公開された最新の問題に
チャレンジしてみました。
1位を取れるかと思いながらワクワクして挑戦したのですが、
私が解答を得た時点での正解者はすでに24人もいました。。。orz
70分くらいかけてやっと答えにたどり着いたのですが、
なんと1位の人(しかも日本人!)は12分足らずで
解答を導き出したようでした。
是非お近づきになりたいものです。


問題はこちらです。
Problem 288
Problem 288(原文)


なんとか最適化して 27.969 [sec] で実行できましたが、
解答した時点では 73.641 [sec] もかかるダメプログラムでした。
次回こそは1位目指して頑張りたいです。
(そして自分にご褒美を…ッ!)


今回の肝となるのは
N(p,q) や Nfac(p, q) の値を計算したら負け、
ということに尽きると思います。
「N! が p で何回割れるか」を計算する方法として

[N/p] + [N/p**2] + [N/p**3] + ... 
(ただし [x] はガウス記号。xを超えない最大の整数を表す。)

という式を使うのもミソと言えばミソですが、
これはまぁ高校数学の範囲なので
どうでも良いと言えばどうでも良いですね。


すっかりProject Eulerのトリコです。
来月開催されるGoogle Code Jamのための準備として
なまっている頭をピチピチの状態に戻したいと思います。


私が書いたコードはコチラです。

# -*- coding: utf-8 -*-

import time
_S = time.time()

# for sample
#P = 3
#Q = 10 ** 4
#B = 20
#DIV = P ** B

P = 61
Q = 10 ** 7
B = 10
DIV = P ** B

ret = 0

m = 1
S = 290797
for tid in xrange(1, Q + 1):
    S = S * S % 50515093
    T = S % P
    ret += T * m
    if tid < B:
        m = (m * P + 1)

print ret % DIV

print '%.3f [sec]' % (time.time() - _S)