http://acm.nyist.net/JudgeOnline/problem.php?pid=34提交地址

韓信點兵-中國剩余定理。

題目能夠用枚舉非常easy的做出來，在這里寫是為了運用一下剛剛學習的中國剩余定理。

曾經寫過中國剩余定理的博客在這就不多說了。

假設以下的字母看不懂請看我的還有一篇博客http://blog.csdn.net/u010123208/article/details/24314627

說一說思路吧。

1.首先我們要用數組存儲我們的要的除數。和余數。

我們用m[]來存儲，余數我們用a[]來存儲。

2.接下來我們要計算M了 ，然后是mi mi的值我用mm[]來存儲的。

3.如今基本的任我就是計算mi的逆元了。

計算逆元我們當然要用擴展歐幾里得定理了。注意在用擴展歐幾里得定理的時候我們會遇到這種問題，返回的結果是個負數。舉個樣例就是 m1的逆元 ?mm[1]x + m[1]y = 1；返回x=-1，y=12，這個但是這不是我們想要的數值。我們能夠用m[1]+x = 2; mm[1]-y=23;（這個結論是我在群里問他們，他們說自己計算一下。詳細的也沒說。我就突然想到這樣來計算試試，結果真行。我又試了幾個，也行，這詳細如何我也不知道。希望有看到博客對擴展歐幾里得定理比較清楚的給我留下言，我請教一下。在這謝謝了）。

4 我們須要的東西都已經求出來了。我們就能夠計算結果了。（假設不知道請看我的還有一篇博客中介紹的）

以下貼出代碼，代碼僅僅是為了練習而已，對于上面的題目而言，提交肯定會錯的，由于。。

。可是僅僅對于我們的中國剩余定理來時是正確的。

#include<iostream> using namespace std; int exgcd(int i,int j,int &ansx,int &ansy) //擴展歐幾里得定理 { int d = i; if(j==0) { ansx=1; ansy=0; return d; } d=exgcd(j,i%j,ansx,ansy); int temp = ansx; ansx=ansy; ansy=temp-(i/j)*ansy; return d; } int main() {int a[4];//余數for(int i=1;i<4;i++)cin>>a[i];int m[4]={0,3,5,7};//取模的數 質數int mm[4]={0,35,21,15};int t[4];//逆元for(int i=1;i<4;i++){int x,y;exgcd(mm[i],m[i],x,y);if(x<0)x=m[i]+x;t[i]=x;}int sum=0;for(int i=1;i<4;i++){sum=sum+t[i]*a[i]*mm[i];}cout<<sum%105<<endl;system("pause"); }好了！

感謝自己堅持。

轉載于:https://www.cnblogs.com/mengfanrong/p/5186838.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的韩信点兵-中国剩余定理（练习）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。