Python解中国剩余定理（孙子定理）

中国剩余定理（Chinese Remainder Theorem，CRT）又称孙子定理，是数论中的一个定理。
古典数学问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
白话文就是：某物的数量除以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)]))