精品国产乱码久久久久久郑州公司 ,久久九九精品99国产精品,久久久精品人妻一区二区三区蜜桃

數論(4)--------求解模線性方程

求解模線性方程 axºb(mod n)

1.必備知識：擴展歐幾里得算法的知識，可查看我的數論(3)------擴展歐幾里得算法

2.基本思路：

   設d=gcd(a,n)，用擴展歐幾里得算法解線性方程 ax'+ny'=d.
     如果d|b,則方程axºb(mod n)有一個解的值x0=x'(b/d)mod n

   算法導論里說：（還沒理解）
   方程axºb(mod n)有解（即存在d|b,其中d=gcd(a,n)),x0是該方程的任意一個解，則該方程對模n恰有d個不同的
   解，分別為 x(i)=x(0)+i(n/d)(i=1,2,...d).
   特別的設e=x0+n，方程ax=b(mod n)的最小整數解x1=e mod (n/d),最大整數解x2=x1+(d-1)*(n/d)。

   所以實際上用歐幾里得算法記得x'就可以知道結果了。

3.源代碼模板

//擴展歐幾里得算法
2

int Extended_Euclid(int a,int b,int& x,int &y)
3

{
4

if(b==0){
5

x=1;
6

y=0;
7

return a;
8

}
9

int d=Extended_Euclid(b,a%b,x,y);
10

int temp=x;x=y;y=temp-a/b*y;
11

return d;
12

}

//用擴展歐幾里得解模線性方程ax=b (mod n)
2

bool modularLinearEquation(int a,int b,int n)
3

{
4

int x,y,x0,i;
5

int d=Extended_Euclid(a,n,x,y);
6

if(b%d)
7

return false;
8

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

for(i=1;i<=d;i++)
10

printf("%d\n",(x0+i*(n/d))%n);
11

return true;
12

}
13

posted on 2009-09-05 19:49 原語餓狼閱讀(1349) 評論(0) 編輯收藏引用所屬分類: 數論

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

相關文章: 數論(4)--------求解模線性方程數論(3)-------歐拉phi函數數論(2)-------擴展歐幾里得算法數論(1)-----歐幾里得算法

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

yuanyuelang

導航

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

最新評論

數論(4)--------求解模線性方程