The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

中國剩余定理

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstdio>

using namespace std;

int EXTENDED_EUCLID(int a,int b,int &x,int &y)//擴展歐幾里德算法

{

if(b==0)

{

x=1;

y=0;

return a;

}

int r=EXTENDED_EUCLID(b,a%b,x,y);

int temp=x;

x=y;

y=temp-a/b*y;

return r;

}

int MODULAR_LINEAR(int a,int b,int n)//求解模線性方程

{

int d,x,y;

int x0;

d=EXTENDED_EUCLID(a,n,x,y);

x0=(x*(b/d)+n)%n;

return x0;

}

int CHINESE_RESIDUE_THEOREM(int n[],int b[],int k)//求解模線性方程組，所有數據從1號下標開始存儲

{

int result=0;

int i;

int N=1;

int *m=new int [k+1];

int *reversem=new int [k+1];

int sum=0;

for(i=1;i<=k;i++)

{

N*=n[i];

}

for(i=1;i<=k;i++)

{

m[i]=N/n[i];

reversem[i]=MODULAR_LINEAR(m[i],1,n[i]);

sum+=m[i]*reversem[i]*b[i];

}

result=sum%N;

return result;

}

int main ()

{

int num;

int i;

printf("參考格式:X mod n[i] = b[i]\n");

cout<<"請輸入方程的個數：";

cin>>num;

int *n=new int [num+1];

int *b=new int [num+1];

for(i=1;i<=num;i++)

{

cout<<"請輸入第"<<i<<"個方程的n和b:";

cin>>n[i]>>b[i];

}

int result=CHINESE_RESIDUE_THEOREM(n,b,num);

cout<<"解為:";

cout<<result<<endl;

cout<<"謝謝你的使用"<<endl;

system("pause");

return 0;

}

至于擴展歐幾里德的通解可以看轉到博客里的一篇文章

posted on 2009-07-14 16:27 abilitytao 閱讀(189) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

中國剩余定理