专栏首页编程坑太多Python解中国剩余定理(孙子定理)

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)]))

本文分享自微信公众号 - 编程坑太多(idig88),作者:互联网

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python os模块详解

    IT故事会
  • 最主流的SSM实现的通用权限管理系统

    IT故事会
  • 「走进k8s」如何初体验Kubernetes(12)

    PS:(梳理概念)pod里面包括N个容器,service里面包括pod,Deployment可能包括service或者是pod。

    IT故事会
  • weex-17-组件list

    我们根据数组动态的添加子区域,这里我们要使用到组件cell,当列表上数据比较多时,使用cell能够更高效的管理内存和组件重用

    酷走天涯
  • Python Data Structures - C2 Sort

    参考内容: 1.Problem Solving with Python Chapter5: Search and Sorting online_link ...

    宅男潇涧
  • 这里有一份Node.js入门指南和实践,请注意查收

    JS 是脚本语言,脚本语言都需要一个解析器才能运行。对于写在 HTML 页面里的 JS,浏览器充当了解析器的角色。而对于需要独立运行的 JS,NodeJS 就是...

    null仔
  • Redis类型之lists类型

    9、rpoplpush 从第一个list的尾部移除元素并添加到第二个list的头部,最后返回被移除的元素值,整个操作是原子的,如果第一个list是空或者不存在...

    人生不设限为梦想时刻准备着
  • 性能测试之吞吐量

    我们每天的生活中都在用水用电,我只会关心自己的水管是否有水,水压是否稳定,如果我们把水龙头拧到最大,还是一滴一滴的流水。那我们就要愤怒了,直接找房东问明情况。我...

    流柯
  • 基于Django的电子商务网站开发(连载26)

    登录用户通过调用语句my_chart_list= util.add_chart(request)把商品放入购物车中。在产品代码Util类中的add_chart(...

    小老鼠
  • 物联网(IoT)中的“物(Things)”

    构成新兴“物联网”的“事物”的范围从拖拉机到恒温器再到运输集装箱。当我们使计算机联机,然后随着智能手机的兴起,互联网改变了世界。想象一下,当连接遍及我们日常生活...

    用户4122690

扫码关注云+社区

领取腾讯云代金券