k-sunakoの技術ログ

def alg10_20(cs, i_s, i_e, M, i_r0, j_r0):
    if i_e - i_s == 1:
        return cs[i_s]
    else:
        return M[i_r0][j_r0+1] * alg10_20(cs, i_s, i_s+(i_e-i_s)//2, M, i_r0-1, 2*j_r0) \
             + M[i_r0][j_r0]  *  alg10_20(cs, i_s+(i_e-i_s)//2, i_e, M, i_r0-1, 2*j_r0+2)

ms = [2, 3, 5, 7, 11, 13, 17, 19]
ms, r, k = pack_ms(ms)
M = alg10_3(ms)
cs = list(range(len(ms)))
alg10_20(cs, 0, len(ms), M, -2, 0)

def alg10_18(ms):
    m = functools.reduce(lambda a, b: a*b, ms, 1)
    ms2 = [mi**2 for mi in ms]

    # 1. call alg10_16 (alg10_16はalg10_3とalg10_14を併せたもの)
    M = alg10_3(ms2)
    m_rem_mi2 = alg10_14x(0, len(ms2), m, M, -2, 0)

    # 2. m/mi rem mi
    m_rem_mi = [m_rem2//mi for mi, m_rem2 in zip(ms, m_rem_mi2)]

    # 3. extended euclidean algo
    si = []
    for mi, mi_rem in zip(ms, m_rem_mi):
        a, b = xgcd(mi, mi_rem)
        if 0 < b:
            si.append(b)
        else:
            si.append(b+mi)
    return si

ms = [2, 3, 5, 7, 11, 13, 17, 19]
m = functools.reduce(lambda a, b: a*b, ms, 1)

si = []
for mi in ms:
    for i in range(1, mi):
        if 1 == (i * m//mi) % mi:
            si.append(i)
            break;
si

ms = [2, 3, 5, 7, 11, 13, 17, 19]
ms, r, k = pack_ms(ms)

alg10_18(ms)