MojoでProject Euler 71

https://projecteuler.net/problem=71

0/1と3/7の間で3/7寄りだと(0+3x)/(1+7x)とすればよいです。これで分母が1000000以下になるようにxを定めればよいですが、分母が3で割り切れるならさらにxを大きくできます。
MojoもOptionalが使えますが、TupleがCollectionElementを実装していないから、

Optional[Tuple[Int, Int]]

は使えないです。

import sys


#################### library ####################

fn gcd(m: Int, n: Int) -> Int:
    if n == 0:
        return m
    else:
        return gcd(n, m % n)

# ax = by + 1 (a, b > 0)
fn linear_diophantine(a: Int, b: Int) raises -> Tuple[Int, Int]:
    if a == 1:
        return (1, 0)
    
    var q = b // a
    var r = b % a
    if r == 0:
        raise Error()
    
    var result = linear_diophantine(r, a)
    var x1 = result.get[0, Int]()
    var y1 = result.get[1, Int]()
    return (-q * x1 - y1, -x1)


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

fn f(owned n: Int, owned d: Int, N: Int) -> Int:
    var d1 = gcd(n, d)
    n //= d1
    d //= d1
    try:
        var result = linear_diophantine(n, d)
        var x0 = result.get[0, Int]()
        var y0 = result.get[1, Int]()
        # y = 3m + y0
        var m = (N * n - d * y0 - 1) // (n * d)
        var x = d * m + x0
        var y = n * m + y0
        return y
    except:
        return 0

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