MojoでProject Euler 53

https://projecteuler.net/problem=53

nに対して1000000を超える最小のrとそのときのコンビネーションの値を記憶しておけば、n+1に対するrをO(1)で計算できます。

import sys


#################### process ####################

fn greater_limit(n: Int, prev_min_r: Int, prev_c: Int,
                                            M: Int) -> Tuple[Int, Int]:
    if prev_c == 0:
        var c = 1
        for r in range(1, n//2+1):
            c = c * (n - r + 1) // r
            if c > M:
                return (r, c)
        else:
            return (0, 0)
    else:
        var c = prev_c * n // (n - prev_min_r)
        for r in range(prev_min_r - 1, -1, -1):
            var c1 = c * (r + 1) // (n - r)
            if c1 <= M:
                return (r + 1, c)
            c = c1
        else:
            return (0, 0)   # ここには来ないはず

fn f(N: Int, M: Int) -> Int:
    var s = 0
    var c = 0
    var r = 0
    for n in range(1, N+1):
        var t = greater_limit(n, r, c, M)
        r = t.get[0, Int]()
        c = t.get[1, Int]()
        if r != 0:
            s += n + 1 - 2 * r
    return s

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    var M = atol(args[2])
    print(f(N, M))