Project Euler 160

プロジェクトオイラー
http://projecteuler.net/index.php

Q160.
f(n)をn!の0を除く最後の5桁とする。f(10¹²)を求めよ。

nまでの5で割り切れる数を除いて、かつ2の因子を5つまで取り除いた積をg(n)とする。例えば、

g(6) = 1 * (2/2) * 3 * (4/4) * (6/2) = 9

こうすれば、

f(n) = (g(n) + g(n/5) + g(n/25) + ...) * 2^e

となる。eはnまでの先ほど取り除いた2の因子の数から、5の因子を数を引いたもの。これは簡単に求められる。また、

g(n10⁵) = g(10⁵)ⁿ

だから、g(10⁵)さえわかっていれば、バイナリ法で簡単に求められる。

def five_digits(n):

    while n % 10 == 0:

        n /= 10

    return n % M
def f(n):

    m = pow(2, count_pE(n, 2) - count_p(n, 5))

    while n:

        m = mul(m, g(n))

        n /= 5

    

    return m
def g(n):

    return mul(ary_g[n%M], pow(ary_g[M], n / M))
def remove_p(n, p):

    while n % p == 0:

        n /= p

    return n
# up to E

def remove_pE(n, p):

    for i in range(E):

        if n % p:

            break

        n /= p

    return n
def count_p(n, p):

    m = 0

    while n >= p:

        n /= p

        m += n

    return m
def count_pE(n, p):

    m = 0

    for i in range(E):

        n /= p

        m += n

    return m
def make_g(n):

    a = [ 1 ] * (n + 1)

    m = 1

    for k in xrange(1, n + 1):

        if k % 5:

            m = mul(m, remove_p(remove_pE(k, 2), 5))

        a[k] = m

    return a
def mul(x, y):

    return five_digits(x * y)
def pow(n, e):

    if e == 0:

        return 1

    

    m = pow(n, e / 2)

    m = mul(m, m)

    if e % 2 == 1:

        m = mul(m, n)

    return m
N = 10 ** 12

E = 5

M = 10 ** E

ary_g = make_g(M)

print f(N)