澳门新蒲京娱乐


0框架事务处理操作简单示例【新蒲京官方下载】,thinkPHP框架中执行事务的方法示例

【新蒲京官方下载】自动生成编号

欧几里德与扩展欧几里德算法的理解,扩展欧几里德算法

原创

理解:问度娘  1、欧几Reade  2、实行欧几Reade

欧几Reade算法是用来求最大左券数的:

浅析:

转载自:

1 int gcd(int a,int b)2 {3   return b==0?a:gcd(b,a%b);4 }

欧几Reade算法

欧几Reade算法又称辗转相除法,用于计算八个整数a,b的最大左券数。

着力算法:设a=qb+r,当中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。

先是种证明:

     
a能够代表成a = kb + r,则r = a mod b

  倘若d是a,b的叁个左券数,则有

  d|a,
d|b,而r = a – kb,因此d|r

  由此d是(b,a
mod b)的公约数

  假诺d
是(b,a mod b)的合同数,则

  d | b
, d |r ,但是a = kb +r

  由此d也是(a,b)的左券数

  因而(a,b)和(b,a
mod b)的左券数是一致的,其最大左券数也决然相等,得证

 

第三种表明:

   
要证欧几Reade算法成立,即证: gcd(a,b)=gcd(b,r),在那之中gcd是取最大合同数的情趣,r=a mod b

   
下面证 gcd(a,b)=gcd(b,r)

    设 
c是a,b的最大左券数,即c=gcd(a,b),则有
a=mc,b=nc,当中m,n为正整数,且m,n互为质数

    由 r=
a mod b可见,r= a- qb 个中,q是正整数,

    则
r=a-qb=mc-qnc=(m-qn)c

   
b=nc,r=(m-qn)c,且n,(m-qn)互质(假如n,m-qn不互质,则n=xd, m-qn=yd
当中x,y,d都是正整数,且d>1

                                                               
则a=mc=(qx+y)dc, b=xdc,那时a,b
的最大左券数变成dc,与前提争持,

                                                                
所以n ,m-qn一定互质)

   
则gcd(b,r)=c=gcd(a,b)

   
得证。

 

算法的贯彻:

最简易的章程正是行使递归算法,代码如下:

1 int gcd(int a,int b)
2 {
3     if(b==0)
4         return a;
5     return 
6         gcd(b,a%b);
7 }

代码可优化如下:

1 int gcd(int a,int b)
2 {
3     return b ? gcd(b,a%b) : a;
4 }

自然你也得以用迭代式样:

 

 1 int Gcd(int a, int b)
 2 {
 3     while(b != 0)
 4     {
 5     int r = b;
 6     b = a % b;
 7     a = r;
 8     }
 9     return a;
10 }

 

 

推而广之欧几Reade算法描述为:已知a,
b求解一组x,y,使它们满意贝祖等式: ax+by =
gcd =d(解一定期存款在,依照数论中的相关定理)。

 

恢宏欧几Reade常用在求解模线性方程及方程组中。

扩展欧几里德算法

骨干算法:对于不完全为
0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大合同数,必然存在整数对
x,y ,使得 gcd(a,b)=ax+by。

证明:设
a>b。

  1,显然当
b=0,gcd(a,b)=a。此时 x=1,y=0;

  2,ab!=0

  设
ax1+by1=gcd(a,b);

  bx2+(a mod
b)y2=gcd(b,a mod b);

  依据朴素的欧几Reade原理有
gcd(a,b)=gcd(b,a mod b);

  则:ax1+by1=bx2+(a
mod b)y2;

  即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;

  根据恒等定理得:x1=y2;
y1=x2-(a/b)*y2;

   
 那样我们就获取了求解 x1,y1 的艺术:x1,y1 的值基于 x2,y2.

 
 上边包车型的士驰念是以递归定义的,因为 gcd 不断的递归求解一定会有个时候
b=0,所以递归能够了结。

 

推而广之欧几Reade的递归代码:

 

 1 int exgcd(int a,int b,int &x,int &y)
 2 {
 3     if(b==0)
 4     {
 5         x=1;
 6         y=0;
 7         return a;
 8     }
 9     int r=exgcd(b,a%b,x,y);
10     int t=x;
11     x=y;
12     y=t-a/b*y;
13     return r;
14 }

 

庞大欧几里德非递归代码:

 

 1 int exgcd(int m,int n,int &x,int &y)
 2 {
 3     int x1,y1,x0,y0;
 4     x0=1; y0=0;
 5     x1=0; y1=1;
 6     x=0; y=1;
 7     int r=m%n;
 8     int q=(m-r)/n;
 9     while(r)
10     {
11         x=x0-q*x1; y=y0-q*y1;
12         x0=x1; y0=y1;
13         x1=x; y1=y;
14         m=n; n=r; r=m%n;
15         q=(m-r)/n;
16     }
17     return n;
18 }

 

扩展欧几Reade算法的施用关键有以下三方面:

(1)求解不定方程;

(2)求解模线性方程(线性同余方程);

(3)求解模的逆元;

 

(1)使用扩充欧几里德算法消除不定方程的方法:

 
对于不定整数方程pa+qb=c,若 c mod Gcd(p,
q)=0,则该方程存在整数解,不然空中楼阁整数解。

 
上边已经列出找二个整数解的艺术,在找到p * a+q * b = Gcd(p,
q)的一组解p0,q0后,p * a+q * b = Gcd(p,
q)的其他整数解满意:

**  p = p0

  • b/Gcd(p, q) * t    q = q0
  • a/Gcd(p, q) * t(在那之中t为跋扈整数)  
    至于pa+qb=c的大背头解,只需将p * a+q * b = Gcd(p, q)的种种解乘上
    c/Gcd(p, q) 就可以。**

  在找到p
* a+q * b = Gcd(a, b)的一组解p0,q0后,应该是收获p * a+q * b =
c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b)),

  p *
a+q * b = c的别样整数解满意:

**  p = p1

  • b/Gcd(a, b) * t**

**  q = q1

  • a/Gcd(a, b) * t(个中t为大肆整数)**

  p
、q就是p * a+q * b = c的有所整数解。

连带表达可参照:

 

用扩充欧几里得算法解不定方程ax+by=c;

代码如下:

1 bool linear_equation(int a,int b,int c,int &x,int &y)
2 {
3     int d=exgcd(a,b,x,y);
4     if(c%d)
5         return false;
6     int k=c/d;
7     x*=k; y*=k;    //求得的只是其中一组解
8     return true;
9 }

(2)用扩张欧几Reade算法求解模线性方程的法子:

   
同余方程 ax≡b (mod n)对于未确定的数 x 有解,当且仅当 gcd(a,n) |
b。且方程有解时,方程有 gcd(a,n) 个解。

   
求解方程 ax≡b (mod n) 也便是求解方程 ax+ ny= b, (x, y为整数)

    设 d=
gcd(a,n),如果整数 x 和 y,满意 d= ax+ ny(用扩大欧几Reade得出)。假使 d|
b,则方程

    a*
x0+ n* y0= d, 方程两侧乘以 b/ d,(因为 d|b,所以能够整除),获得 a*
x0* b/ d+ n* y0* b/ d= b。

    所以
x= x0* b/ d,y= y0* b/ d 为 ax+ ny= b 的三个解,所以 x= x0* b/ d 为
ax= b (mod n ) 的解。

    ax≡b
(mod n)的一个解为 x0= x* (b/ d ) mod n,且方程的 d 个解分别为 xi= (x0+
i* (n/ d ))mod n {i= 0… d-1}。

   
设ans=x*(b/d),s=n/d;

   
方程ax≡b (mod n)的纤维整数解为:(ans%s+s)%s;

   
相关申明:

 
  注解方程有一解是: x0 = x'(b/d) mod n;

   
由 a*x0 = a*x'(b/d) (mod n)

         a*x0 =
d (b/d) (mod n)   (由于 ax’ = d (mod n))

                 =
b (mod n)

 
  注明方程有d个解: xi = x0 + i*(n/d)  (mod n);

    由
a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)

                             =
(a*x0+a*i*(n/d)) (mod n)

                             =
a * x0 (mod n)             (由于 d | a)

                             =
b

   
 

第一看一个简便的例证:

5x=4(mod3)

解得x =
2,5,8,11,14…….

经过可以窥见叁个原理,正是解的间距是3.

那么那些解的距离是怎么调节的呢?

假如能够主见找到第七个解,何况求出解之间的间隔,那么就足以求出模的线性方程的解集了.

我们设解之间的距离为dx.

那么有

a*x =
b(mod n);

a*(x+dx)
= b(mod n);

两式相减,获得:

a*dx(mod
n)= 0;

也正是说a*dx正是a的倍数,同有的时候间也是n的翻番,即a*dx是a
和 n的公倍数.为了求出dx,大家相应求出a 和
n的最小公倍数,此时对应的dx是比一点都不大的.

设a 和
n的最大公约数为d,那么a 和 n 的最小公倍数为(a*n)/d.

即a*dx =
a*n/d;

所以dx =
n/d.

因此解之间的间距就求出来了.

   
代码如下:

 

 1 bool modular_linear_equation(int a,int b,int n)
 2 {
 3     int x,y,x0,i;
 4     int d=exgcd(a,n,x,y);
 5     if(b%d)
 6         return false;
 7     x0=x*(b/d)%n;   //特解
 8     for(i=1;i<d;i++)
 9         printf("%d\n",(x0+i*(n/d))%n);
10     return true;
11 }

 

(3)用欧几Reade算法求模的逆元:

     
 同余方程ax≡b (mod n),假使 gcd(a,n)== 1,则方程独有唯一解。

     
在这种气象下,假如 b== 1,同余方程正是 ax=1 (mod n ),gcd(a,n)=
1。

     
那时称求出的 x 为 a 的对模 n 乘法的逆元。

     
对于同余方程 ax= 1(mod n ), gcd(a,n)= 1 的求解正是求解方程

      ax+
ny= 1,x, y
为整数。那些可用扩大欧几Reade算法求出,原同余方程的独一解正是用扩大欧几Reade算法得出的
x

求解x,y的代码如下:

应用标题:

洛谷P1082
同余方程

 1 int gcd(int a,int b)    //扩展欧几里德  2 { 3     int d; 4     if(b==0) 5     { 6         x=1; 7         y=0; 8         return a; 9     }10     else11     {12         d=gcd(b,a%b);13         int temp;14         temp=x;15         x=y;16         y=temp-*y;17         return d;18     }19 } 

难点汇报

求关于 x 的同余方程 ax ≡ 1 (mod b)的纤维正整数解。

已知
a*x+b*y==gcd,gcd==gcd,将
gcd 代入a*x+b*y
可得**

输入输出格式

输入格式:

输入独有一行,包蕴八个正整数 a, b,用三个空格隔开分离。

输出格式:

出口独有一行,包括八个正整数 x0,即最小正整数解。输入数据保险一定有解。

**b*x1+*y1==a*x+b*y( 注意, 和是见仁见智的 ,**
**下层的递归值****

输入输出样例

输入样例#1:

3 10

输出样例#1:

7

**下一场大家供给精通三个公式,a%b==a-*b,将上式变形得 b*x1+*b
)*y1==a*x+b*y,整理可得 a*y1+b**y)==a*x+b*y;**

说明

【数据范围】

对于 40%的数据,2 ≤b≤ 1,000;

对于 60%的数据,2 ≤b≤ 50,000,000;

对于 100%的数据,2 ≤a, b≤ 2,000,000,000。

NOIP 2012 提高组 第二天 第一题

 1 #include<bits/stdc++.h>  
 2 using namespace std;  
 3 int gcd(int a, int b, int &x, int &y) {  
 4     if(b==0){x=1;y=0;return a;}
 5     else{  
 6         int r=gcd(b,a%b,x,y);  
 7         int t=x-a/b*y;  
 8         x=y;y=t;  
 9         return r;  
10     }  
11 }  
12 int main()
13 {  
14     int a,b,x,y;  
15     cin>>a>>b;  
16     gcd(a,b,x,y);  
17     while(x<0)x+=b;
18     cout<<x;  
19     return 0;  
20 }  

 

 

**通过我们能够:**

**x==y1;**

**y==**x1-*y;**

当递归到底层时,此时 b==0
,进而能自由的摄取gcd==a,x==1,y==0;知道了最尾巴部分的,大家就足以依赖公式递归回去求上边层的。

相关文章

No Comments, Be The First!
近期评论
    功能
    网站地图xml地图