国产精品成人99久久久久 ,亚洲精品久久久www,国产精品毛片久久久久久久

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

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

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

2.基本思路：

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

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

   所以實(shí)際上用歐幾里得算法記得x'就可以知道結(jié)果了。

3.源代碼模板

//擴(kuò)展歐幾里得算法
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

}

//用擴(kuò)展歐幾里得解模線性方程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) 評(píng)論(0) 編輯收藏引用所屬分類: 數(shù)論

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

yuanyuelang

導(dǎo)航

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

最新評(píng)論

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