Project Euler 169

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

Q169.
10²⁵を2のべきで分割する方法の個数。ただし、1もOK、同じ数は2つまで。

普通に、再帰で書ける。大きい数から使っていき、それがあと何回使えるかで関数にする。2^m以下しか使えないとき、2^m+2-2までにしかならないので、それでかなり絞り込める。また、まともに再帰だと時間がかかるので、一度計算した結果は辞書に入れておく。

def g(n, m, k):

    if n == 1:

        return 1

    elif m == 0:

        if n == 2 and k == 2:

            return 1

        else:

            return 0

    

    if (n, m, k) in g_dic:

        return g_dic[(n,m,k)]

    

    s = 0

    for e in range(m, -1, -1):

        if e == m and k == 1:

            if (1 << e) * 3 < n + 2:

                break

        else:

            if 1 << e + 2 < n + 2:

                break

        p = 1 << e

        if p == n:

            s += 1

        elif p < n:

            if e == m and k == 1:

                s += g(n - p, e - 1, 2)

            else:

                s += g(n - p, e, 1)

    

    g_dic[(n,m,k)] = s

    return s
def f(n):

    e = 0

    while n >> e:

        e += 1

    return g(n, e - 1, 2)
g_dic = { }

N = 10 ** 25

print f(N)