tmp.py

# included from libs/crt.py
"""
Chinese Remainder Theorem
"""

# included from libs/extended_euclidean.py
"""
Extended Euclidean algorithm
"""


def extended_euclidean(a, b, test=False):
    """
    Given a, b, solve:
    ax + by = gcd(a, b)
    Returns x, y, gcd(a, b)

    Other form, for a prime b:
    ax mod b = gcd(a, b) = 1

    >>> extended_euclidean(3, 5, test=True)
    3 * 2 + 5 * -1 = 1 True
    >>> extended_euclidean(240, 46, test=True)
    240 * -9 + 46 * 47 = 2 True

    Derived from https://atcoder.jp/contests/acl1/submissions/16914912
    """
    init_a = a
    init_b = b
    s, u, v, w = 1, 0, 0, 1
    while b:
        q, r = divmod(a, b)
        a, b = b, r
        s, u, v, w = v, w, s - q * v, u - q * w

    if test:
        print(f"{init_a} * {s} + {init_b} * {u} = {a}",
              init_a * s + init_b * u == a)
    else:
        return s, u, a


# end of libs/extended_euclidean.py

def crt(a, m, b, n):
    """
    Find x s.t. x % m == a and x % n == b

    >>> crt(2, 3, 1, 5)
    11
    >>> crt(1, 4, 3, 6)
    9
    """
    x, y, g = extended_euclidean(m, n)
    if g == 1:
        return (b * m * x + a * n * y) % (m * n)
    s = (b - a) // g
    return (a + s * m * x) % (m * n // g)

# end of libs/crt.py


def test(a=712158808933002481389578163771, b=7, c=41):
    from fractions import Fraction
    numer = int(str(a) + str(b))
    denom = int(str(c) + str(a))

    nd = Fraction(numer, denom)
    cb = Fraction(b, c)
    if nd == cb:
        print(f"{a}_{b} / {c}_{a} = {nd}")


for b in range(1, 10):
    for c in range(11, 100):
        if c == 10 * b:
            continue
        bc = b * c
        MOD1 = 1_000_000_007
        MOD9 = 998_244_353
        for n in range(2, 18):
            d = bc * (10 ** n - 1)
            e = b - c * 10
            einv1 = pow(e, -1, MOD1)
            a1 = -d * einv1
            einv9 = pow(e, -1, MOD9)
            a9 = -d * einv9
            a = crt(a1, MOD1, a9, MOD9)
            test(a, b, c)