Python實(shí)現(xiàn)的中國(guó)剩余定理算法示例
本文實(shí)例講述了Python實(shí)現(xiàn)的中國(guó)剩余定理算法。分享給大家供大家參考，具體如下：
中國(guó)剩余定理（Chinese Remainder Theorem-CRT）:又稱(chēng)孫子定理，是數(shù)論中的一個(gè)定理。即如果一個(gè)人知道了一個(gè)數(shù)n被多個(gè)整數(shù)相除得到的余數(shù)，當(dāng)這些除數(shù)兩兩互質(zhì)的情況下，這個(gè)人就可以唯一的確定被這些個(gè)整數(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，說(shuō)明概述最小為1，之后該條件一直滿(mǎn)足，所以需要加上的數(shù)一定是2的倍數(shù)。被3除余2，即（1+2*i）%3=2，其中i為正整數(shù)。之后該條件一直滿(mǎn)足，所以需要加上的數(shù)一定是3的倍數(shù)，又因?yàn)榍耙粋€(gè)條件的限制，所以是2和3的最小公倍數(shù)的整數(shù)倍。一次類(lèi)推，知道找到被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
最終結(jié)果為119。
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要為大家介紹了Python全棧之MySQL，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-01-01
這篇文章主要介紹了python中的list字符串元素排序方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
Jupyter Notebook是基于網(wǎng)頁(yè)的用于交互計(jì)算的應(yīng)用程序,Jupyter notebook,作為Python廣受歡迎的一款I(lǐng)DLE,其直觀(guān)性、簡(jiǎn)易性、易于閱讀等優(yōu)點(diǎn)廣受許多Python用戶(hù)所推薦,這篇文章介紹Jupyter中markdown的操作,感興趣的朋友一起看看吧2024-01-01
python3設(shè)計(jì)模式之簡(jiǎn)單工廠(chǎng)模式
這篇文章主要為大家詳細(xì)介紹了python3設(shè)計(jì)模式之簡(jiǎn)單工廠(chǎng)模式，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-10-10
Matplotlib實(shí)戰(zhàn)之直方圖繪制詳解
直方圖,又稱(chēng)質(zhì)量分布圖,用于表示數(shù)據(jù)的分布情況,是一種常見(jiàn)的統(tǒng)計(jì)圖表,這篇文章主要為大家詳細(xì)介紹了如何使用Matplotlib繪制直方圖,需要的可以參考下2023-08-08
這篇文章主要介紹了Pytorch 使用不同版本的cuda的方法步驟，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
Python Scrapy框架：通用爬蟲(chóng)之CrawlSpider用法簡(jiǎn)單示例
這篇文章主要介紹了Python Scrapy框架：通用爬蟲(chóng)之CrawlSpider用法,結(jié)合實(shí)例形式分析了Scrapy框架中CrawlSpider的基本使用方法,需要的朋友可以參考下2020-04-04
理解 pandas 的函數(shù)，要對(duì)函數(shù)式編程有一定的概念和理解，下面這篇文章主要給大家介紹了關(guān)于pandas提升計(jì)算效率的相關(guān)資料，需要的朋友可以參考下2021-05-05
詳解Python查找算法的實(shí)現(xiàn)(線(xiàn)性,二分,分塊,插值)
這篇文章主要為大家介紹了Python中常見(jiàn)的四種查找算法的實(shí)現(xiàn)：線(xiàn)性、二分、分塊和插值，文中通過(guò)圖片詳細(xì)講解了它們實(shí)現(xiàn)的原理與代碼，需要的可以參考一下2022-04-04
今天小編就為大家分享一篇PyTorch 普通卷積和空洞卷積實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-01-01