Pythonは中国の残りの定理を解く(孫の定理)

1016 ワード

中国の残りの定理(Chinese Remainder Theorem,CRT)は孫の定理とも呼ばれ、数論の一つの定理である.古典数学の問題:あるものはその数を知らないで、三三数の残りの2、五五数の残りの3、七七数の残りの2.問物幾何学?白話文は、ある物の数を3余り2で割って、5余り3で割って、7余り2で割って、ある物の数はいくらですか?
次のアルゴリズムにエラーがあります.
#!/usr/bin/env python
from functools import reduce


def egcd(a, b):
    """      """
    if 0 == b:
        return 1, 0, a
    x, y, q = egcd(b, a % b)
    x, y = y, (x - a // b * y)
    return x, y, q


def chinese_remainder(pairs):
    """      """
    mod_list, remainder_list = [p[0] for p in pairs], [p[1] for p in pairs]
    mod_product = reduce(lambda x, y: x * y, mod_list)
    mi_list = [mod_product//x for x in mod_list]
    mi_inverse = [egcd(mi_list[i], mod_list[i])[0] for i in range(len(mi_list))]
    x = 0
    for i in range(len(remainder_list)):
        x += mi_list[i] * mi_inverse[i] * remainder_list[i]
        x %= mod_product
    return x


if __name__=='__main__':
    print(chinese_remainder([(3, 2), (5, 3), (7, 2)]))