Python實現(xiàn)的中國剩余定理算法示例
本文實例講述了Python實現(xiàn)的中國剩余定理算法。分享給大家供大家參考，具體如下：
中國剩余定理（Chinese Remainder Theorem-CRT）:又稱孫子定理，是數(shù)論中的一個定理。即如果一個人知道了一個數(shù)n被多個整數(shù)相除得到的余數(shù)，當這些除數(shù)兩兩互質的情況下，這個人就可以唯一的確定被這些個整數(shù)乘積除n所得的余數(shù)。
維基百科上wiki：The Chinese remainder theorem is a theorem of number theory, which states that, if one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.
有一數(shù)n，被2除余1，被3除余2，被5除余4，被6除余5，正好被7整除，求該數(shù)n.
分析：n被2除余1，說明概述最小為1，之后該條件一直滿足，所以需要加上的數(shù)一定是2的倍數(shù)。被3除余2，即（1+2*i）%3=2，其中i為正整數(shù)。之后該條件一直滿足，所以需要加上的數(shù)一定是3的倍數(shù)，又因為前一個條件的限制，所以是2和3的最小公倍數(shù)的整數(shù)倍。一次類推，知道找到被7整除的數(shù)。
n=1 while(n%3 != 2): n += 2 while(n%5 != 4): n += 6 while(n%6 != 5): n += 30 while(n%7 != 0): n += 30
最終結果為119。
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結構與算法教程》、《Python函數(shù)使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設計有所幫助。
相關文章
python?yaml文件數(shù)據(jù)按原有的數(shù)據(jù)順序dump問題小結
這篇文章主要介紹了python?yaml文件數(shù)據(jù)按原有的數(shù)據(jù)順序dump,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2023-11-11
這篇文章主要介紹了微信公眾號接入ChatGPT機器人的方法,不難，總共可以分為兩步，一是在云服務器上部署自定義消息處理服務，二是微信公眾號配置自己的消息處理服務器，本文給大家講解的非常詳細，需要的朋友可以參考下2023-02-02
本文記錄一些 Python 日常編程中的小妙招，并使用 IPython 進行交互測試，讓我們更好的了解和學習 Python 的一些特性，對大家的學習或工作具有一定的價值，需要的朋友可以參考下2021-09-09
這篇文章主要為大家詳細介紹了python?tkinter實現(xiàn)彈窗的輸入輸出，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要介紹了Python中的ctime()方法使用教程,是Python入門學習的基礎知識,需要的朋友可以參考下2015-05-05
PyTorch之nn.ReLU與F.ReLU的區(qū)別介紹
這篇文章主要介紹了PyTorch之nn.ReLU與F.ReLU的區(qū)別介紹，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
這篇文章主要介紹了Python新版極驗驗證碼識別驗證碼，極驗驗證是一種在計算機領域用于區(qū)分自然人和機器人的，通過簡單集成的方式，為開發(fā)者提供安全、便捷的云端驗證服務2023-02-02
在本篇文章中小編給各位整理了關于Python3z中FuzzyWuzzy庫實例用法及相關代碼，有興趣的朋友們可以參考下。2020-11-11
python中字典和列表的使用，在數(shù)據(jù)處理中應該是最常用的，今天通過多種場景給大家分享python 字典和列表嵌套用法，感興趣的朋友一起看看吧2021-06-06
這篇文章主要介紹了Python實現(xiàn)粒子群算法的示例，幫助大家更好的理解和使用Python，感興趣的朋友可以了解下2021-02-02