a mod b)的公约数,枚举显得那么的naïve

    那么,也正是说, a 关于 m
的逆元是三个关于 m
同余的,那么依照最小整数原理,一定期存款在五个细微的正整数,它是 a 关于m
的逆元,而细小的一定是在(0 ,
m)之间的,而且唯有2个,那就好解释了。

 

 

不得不说,我有种不佳的预言,固然考试考到那种裸的数学定理,怕是要完。

   上边的合计是以递归定义的,因为 gcd 不断的递归求解一定会有个时候
b=0,所以递归能够终结。

   联系格局:http://www.cnblogs.com/hadilo/p/5932395.html

        x = y1

  1. int gcd(int a,int b) {             //递归算法  
  2.     return b ? gcd(b, a%b) : a;  
  3. }  
  4.   
  5. int Gcd(inta, int b) {      //迭代算法  
  6.     while(b != 0) {  
  7.         int r = b;  
  8.         b = a%b;  
  9.         a = r;  
  10.     }  
  11.     return a;  
  12. }  

 

   
我们着眼到:欧几Reade算法结束的动静是: a= gcd , b = 0
,那么,那是或不是能给大家求解 x y 提供一种思路呢?因为,那时候,只要 a =
gcd 的周详是 1 ,那么一旦 b 的全面是 0
可能别的值(无所谓是不怎么,反正任何数乘以 0 都卓殊 0 可是a 的周密一定即使1),那时,大家就会有: a*1 + b*0 = gcd

 

    因为当 b=0 时存在 x , y
为末段一组解

能够这么考虑:

  有了那七个定理, 解方程就简单了。

  证明:

        x = x0 + (b/gcd)*t

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

  则原方程解为
x1=x0*c/r , y1=x0*c/r

    欧几Reade有个越发又用的定律:
gcd(a, b) = gcd(b , a%b) ,那样,大家就能够在差不多是 log
的光阴复杂度里求解出来 a 和 b 的最大公约数了,那正是欧几Reade算法,用 C++
语言描述如下:

  2,ab!=0 时

 

            = a*y1 + b*(x1 –
a/b*y1)

  1.     //不定方程  
  2. void linear_equation(int a, int b, int c, int &x, int &y) {  
  3.     int d = exgcd(a, b, x, y);  
  4.     if (c%d)  
  5.         return ;  
  6.     int k = c/d;  
  7.     x *= k; y *= k; // 一组解  
  8.     return ;  
  9. }  

  (未完待续)

    看出哪些来了吧?没错,当gcd(a , m)
!= 1 的时候是未曾解的那也是 a*x + b*y = c 有解的充要条件: c % gcd(a ,
b) == 0

首先扩展欧几里德主要是用来与求解线性方程相关的问题,所以我们从一个线性方程开始分析。现在假设这个线性方程为a*x+b*y=m,如果这个线性方程有解,那么一定有gcd(a,b) | m,即a,b的最大公约数能够整除m(m%gcd(a,b)==0)。证明很简单,由于a%gcd(a,b)==b%gcd(a,b)==0,所以a*x+b*y肯定能够整除gcd(a,b),如果线性方程成立,那么就可以用m代替a*x+b*y,从而得到上面的结论,利用上面的结论就可以用来判断一个线性方程是否有解。
  2.ax+by=Gcd(a, b) 两边同时乘以 m/Gcd(a, b)得a(x*c/Gcd(a,
b))+b(y*c/Gcd(a, b))=m;

                x=(pn+m)k

        y = y0 – a*t

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

    可知:y 与 x-py 互质

        x = x0 + b*t

 

  解得 x1=x0*c/r

    b/gcd 是 b 的因子, a/gcd 是 a
的因数是吗?那么,由于 t的取值范围是整数,你说 (b/gcd)*t 取到的值多还是b*t 取到的值多?同理,(a/gcd)*t 取到的值多依旧 a*gcd
取到的值多?这必将又要问了,那干什么不是更小的数,非得是 b/gcd 和a/gcd

710官方网站, 

  则难题成为用 exgcd 解不定方程

 
  710官方网站 1

  1.对此不定整数方程ax+by=m,若 m mod Gcd(a,
b)=0,则该方程存在整数解,不然不设有整数解。

  亦可伪证 x1<0 的动静:设 x1=-5 ,
s=2

    注意到:大家令 B = b/gcd , A =
a、gcd , 那么,A 和 B 一定是互素的啊?那不就证实了 最小的周详正是 A 和
B
了吗?即使实际还有怎么样不亮堂的,看看《基础数论》(拉斯维加斯海洋大学出版社),那本书把关于不定方程的通解讲的很通晓

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

  设 s=b/r (已评释 b/r
为通解的小小间隔)

   
那些题材也是在先天深夜想通的,想通之后忍不住喷了协调一句弱逼。那是因为:

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

  而那只是更换后的方程的解,原方程的一组解应再
*c/r 转变回去

   
以上便是增添欧几Reade算法的总体历程,照旧用递归写:

代码:

 

   
那就是理论部分,欧几Reade算法部分我们好像只好用来求解最大公约数,不过扩充欧几Reade算法就分歧了,大家既能够求出最大公约数,还能顺便求解出使得:
a*x + b*y = gcd 的通解 x 和 y

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

    则 a=xc , b=yc , 其中x ,
y互质

    这里:

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

    r=a%b=a-pb=xc-pyc=(x-py)c

    那怎么求?能够等价于那样的表达式:
a*x + m*y = 1

算法达成:

 1 inline void exgcd(int a,int b)
 2 {
 3     if (b)
 4         {
 5             exgcd(b,a%b);
 6             int k=x;
 7             x=y;
 8             y=k-a/b*y;
 9         }
10     else y=(x=1)-1;
11 }

    那里,大家称 x 是 a 关于 m
的乘法逆元

  由此(a,b)和(b,a mod b)的公约数是千篇一律的,其最大公约数也必将相等,得证

  方程转换为 ax+by=c 在那之中 y
一般为非正整数

    未来,我们清楚了一定期存款在 x 和 y
使得 : a*x + b*y = gcd , 那么,怎么求出那几个特解 x 和 y
呢?只需求在欧几Reade算法的底子上加点改动就行了。

 

    得证

推而广之欧几里德算法

 

    ax1+by1=bx2+ay2-a/b*by2

   
依旧很不难,相比较欧几Reade算法,只是多加了多少个语句而已。

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

② 、扩充欧几里得算法

原网址:http://blog.csdn.net/zhjchengfeng5/article/details/7786595

 

 

 
  710官方网站 2

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

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

    当 m 是负数的时候,大家取 m
的绝对化值就行了,当 x0 是负数的时候,他模上 m
的结果仍然是负数(在电脑总结的结果上是如此的,尽管定义的时候不是那般的),那时候,大家照样让
x0 对abs(m) 取模,然后结果再增进abs(m)
就行了,于是,大家简单写出上面包车型大巴代码求解三个数 a 对于另一个数 m
的乘法逆元:

有关难题:poj2115 poj2142 poj1061。

  不断算出当层的解并再次来到,最后回到至第1层,获得原解

        y = y0 – (a/gcd)*t

 

五 、excgd 求模的逆元

   
恐怕有人注意到了,那里,小编写通解的时候并不是 x0 + (m/gcd)*t
,可是思想一下就知道了,gcd =
1,所以写了跟没写是一模一样的,不过,由于难题的特殊性,有时候大家赢得的特解
x0 是一个负数,还有个别时候大家的 m 也是一个负数那咋做?

二   扩大欧几里得算法:

  先递归进入下一层,等到到达最后一层即
b=0 时就重返x=1 , y=0

    x 的通解不是 x0 + m*t 吗?

 

  定义 gcd(a,b) 为整数 a 与 b
的最大公约数

 
  710官方网站 3

 算法导论上有三个定理:

    为了生产注脚中的 ax+by=c
,且想达到更小的周详,只可以将 b/r 与 a/r 同除以二个数 s

    为何不是:

  1. //递归代码  
  2. nt exgcd(int a, int b, int&x, int&y) {  
  3.    if (b == 0) {  
  4.        x = 1;  
  5.        y = 0;  
  6.        return a;  
  7.    }  
  8.    int r = exgcd(b, a%b, y, x);  
  9.    int t = x;  
  10.    y = y – a/b*t;  
  11.    return r;  
  12.   
  13.    // 非递归算法  
  14. nt exgcd(int m, int n, int &x, int &y) {  
  15.    int x1, y1, x0, y0;  
  16.    x0 = 1; y0 = 0;  
  17.    x1 = 0; y1 = 1;  
  18.    x = 0; y = 1;  
  19.    int r = m%n;  
  20.    int q = (m-r)/n;  
  21.    while(r) {  
  22.        x = x0 – q*x1;  
  23.        y = y0 – q*y1;  
  24.        x0 = x1; y0 = y1;  
  25.        x1 = x; y1 = y;  
  26.        m = n; n = r; r = m%n;  
  27.        q = (m-r)/n;  
  28.    }  
  29.    return n;  

    解得 x1=y2 , y1=x2-a/b*y2

        gcd = b*x1 +
(a-(a/b)*b)*y1

上边求出的 x(当a>b时)都是最接近0的正整数。(不明白为啥)

         当 b=0 时,gcd(a,b)=a,此时
x=1 , y=0

        y = x1 – a/b*y1

      x0 = x'(b / d)(mod n)

    那么 b/r 与 a/r
就为最小的周详

    什么叫乘法逆元?

  若是d是a,b的3个公约数,则有

  能够依照扩张欧几里得算法求得一组整数解 x0 ,
y0

    大家领会: a%b = a –
(a/b)*b(那里的 “/” 指的是整除,例如 5/2=2 ,
33.33%=0),那么,大家得以进一步赢得:

  1. ll inv(ll a, ll n) {  
  2.     ll d, x, y;  
  3.     d = exgcd(a, n, x, y);  
  4.     return (d == 1) ? (x%n + n)%n : -1;  
  5. }  

  则 x 的小不点儿正整数解为
(x1%s+s)%s

    什么人是欧几Reade?本身百度去

  假诺d 是(b,a mod b)的公约数,则

    ax1+by1=ay2+b(x2-a/b*y2)

    今后大家领悟了 a 和 b
的最大公约数是 gcd ,那么,大家终将能够找到这么的 x 和 y ,使得: a*x +
b*y = gcd
那是三个不定方程(其实是一种丢番图方程),有多解是毫无疑问的,可是倘使我们找到一组优异的解
x0 和 y0 那么,我们就足以用 x0 和 y0 表示出全体不定方程的通解:

   证明:设 a>b。

    因为 y 与 x-py 互质,所以 r 与 b
的最大公约数为 c

    求解形如 a*x +b*y = c
的通解,可是一般从不何人会无聊到让您写出一串通解出来,都是让你在通解中选出一些特殊的解,比如三个数对此另三个数的乘法逆元

 

  当 c%r=0 时,将方程左侧 *r/c 后更换为
ax+by=r 的格局

            = b*x1 + a*y1 –
(a/b)*b*y1

连带题材  hdu1576.

  证明:

 
  710官方网站 4

 

  欧几里得算法,也叫辗转相除,简称
gcd,用于总计五个整数的最大公约数

   
当然那是终极状态,可是大家是或不是能够从最终状态反推到先前时代的状态吧?

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

              即为 x1 加上 3个 s 后的到的细微正整数解

    假诺当前大家要处理的是求出 a 和
b的最大公约数,并求出 x 和 y 使得 a*x + b*y= gcd
,而我辈曾经求出了下三个景况:b 和 a%b 的最大公约数,并且求出了一组x1
和y1 使得: b*x1 + (a%b)*y1 = gcd ,
那么那多个相邻的情事之间是不是留存一种关系吗?

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

版权全部,转发请联系笔者,违者必究

   
还有细微整数解之类的难点,但都是开封小异,只要细心的推一推就出来了,那里就不一一介绍了,下边给一部分标题还有AC代码,仅供参考

一:欧几里得算法(辗转相除法)

    ax1+by1=ay2+bx2-b*a/b*y2

   
由于是用递归写的,所以看起来很简单,也很好回忆。那么哪些是扩充欧几Reade呢?

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

    ax+ab/r*t+by-ab/r*t=c

   
接着乘法逆元讲,一般,大家能够找到无数组解满足条件,不过一般是让你求解出最小的那组解,怎么办?大家求解出来了贰个不一致通常的解
x0 那么,大家用 x0 % m其实就赢得了一点都不大的解了。为啥?

     

                那么此时 a 与 b
的最大公约数为 kc 不为 k

    先介绍怎么着叫做欧几Reade算法

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

    证明:

    相比之前大家的事态:求一组 x 和 y
使得:a*x + b*y = gcd ,是还是不是发现了怎么样?

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

  (此处仍需填补一道模板题,有建议者联系作者

 

代码:

    而b=yc

    有五个数 a b,将来,大家供给 a b
的最大公约数,怎么求?枚举他们的因子?不现实,当 a b
十分大的时候,枚举显得那么的naïve ,那如何是好?

 

  当a%b=0时,gcd(a,b)=b

    扩大欧几Reade有啥样用处呢?

刘汝佳的:

  模板题:http://www.cnblogs.com/hadilo/p/5917173.html

  1. void gcd(int a, int b, int& d, int& x, int& y) {  
  2.     if (!b) {d = a; x = 1; y = 0; }  
  3.     else {gcd(b, a%b, d, y, x); y -= x*(a/b); }  
  4. }  

先感激参考文献:http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

(1)求解不定方程;

  模板题:http://codevs.cn/problem/1212/ 

恢宏欧几Reade算法的运用关键有以下四个地点:

  证明:

 

注:以下研究的数均为整数

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

                则 a=xc=(pn+m)kc ,
b=yc=nkc

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

④ 、exgcd 解线性同余方程

 

联系方式:http://www.cnblogs.com/hadilo/p/5932395.html

证明:

   扩大欧几里得算法,简称
exgcd,一般用来求解不定方程,求解线性同余方程,求解模的逆元等

 

 

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

  再依据 x=y’ , y=x’-a/b/y’ ( x’ 与 y’
为下一层的 x 与 y ) 获得当层的解

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

 

有关题材: hdu2115.

    得证

 

                假设 y 与 x-py
不互质

  定理二:借使方程ax = b(mod n)有解, x0是方程的随意二个解,
则方程对模n恰有d个分歧的解, 分别为: xi = x0 + i * (n / d), 其中 i =
1,2,3……d – 1

  (如
2x+4y=4 转换为 2x+4y=2 后应再将解得的 x , y 乘上2)

 

三 、exgcd
解不定方程(使用不将a与b转为互质的方法)

     证明:

  最新更新停止时间:二零一五-10-11
22:52:11

      那样大家就获得了求解 x1,y1 的章程:x1,y1 的值基于 x2,y2.

    所以第③组的解 x , y
必然存在

代码:

  引理:gcd(a,b)=gcd(b,a%b)

  定理一:设d = gcd(a, n), 假定对整数x’, y’, 有d = ax’ + ny’, 假如d |
b, 则方程ax = b(mod n)有3个解的值为x0, 知足:、

  遵照地方的辨证,在贯彻的时候利用递归做法

     
令a1=a/gcd(a,b),b1=b/gcd(a,b),m1=m/gcd(a,b)。那么x,y的一组解就是x0*m1,y0*m1,但是由于满足方程的解无穷多个,在实际的解题中一般都会去求解x或是y的最小正数的值。以求x为例,又该如何求解呢?还是从方程入手,现在的x,y已经满足a*x+b*y=m,那么a*(x+n*b)+b*(y-n*a)=m显然也是成立的。可以得出x+n*b(n=…,-2,-1,0,1,2,…)就是方程的所有x解的集合,由于每一个x都肯定有一个y和其对应,所以在求解x的时候可以不考虑y的取值。取k使得x+k*b>0,x的最小正数值就应该是(x+k*b)%b,但是这个值真的是最小的吗??如果我们将方程最有两边同时除以gcd(a,b),则方程变为a1*x+b1*y=m1,同上面的分析可知,此时的最小值应该为(x+k*b1)%b1,由于b1<=b,所以这个值一定会小于等于之前的值。在实际的求解过程中一般都是用``while``(x<0)x+=b1来使得为正的条件满足,为了更快的退出循环,可以将b1改为b(b是b1的倍数),并将b乘以一个倍数后再加到x上。

 

 

            
 则 (x1%s+s)%s=(-5%2+2)%2=(-1+2)%2=3%2=1

 

    若 x1<0,因在 C++ 里
a%b=-(-a%b)<0 (a<0 , b>0)  如 -10%4=-2

下边已经列出找八个整数解的方法,在找到 a*x+  b*y = Gcd(a,
b)的一组解x0,y0后,不定方程ax+by=m的一组解满足 x = m(x0)/gcd , y =
m*(y0)/gcd;
据此通解为  x = m*(x0)/gcd + k*lcm/a , y = m*(y0)/gcd + k*lcm/b
(个中k为任意整数);
证明:

    设 r=a%b , c=gcd(a,b)

(1)求解不定方程;

  当
c%r!=0 时无整数解

同余方程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 。

  (在那里发轫编写制定)

  1.    // 模线性方程  
  2. bool modular_linear_equation(int a, int b, int n) {  
  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 = 0; i < d; i++)  
  9.         printf(“%d\n”, (x0 + i*(n/d))%n);  
  10.     return true;  
  11. }  

         则
ax1+by1=bx2+(a-a/b*b)y2

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

  那样大家能够写成递归方式

 

  对于
ax+by=c 的不定方程,设 r=gcd(a,b)

  模板题:http://www.cnblogs.com/hadilo/p/5951091.html

        
则 (x1%s+s)%s=(-(-x1%s)+s)%s=(-(ts-x1)+s)%s=ts-x1 (t∈N)

  关于 x 的模方程 ax%b=c 的解

    得证

    而每一组的解可依照后一组获得

    而 b/r 与 a/r 互质,且 s 为整数,则 s=1
,不影响通解

    若
x1>0,则 (x1%s+s)%s=x1%s%s+s%s=x1%s=x1-ts (t∈N)

    即为 x1 通过加或减上多少个 s
后取得的蝇头正整数解

 

  通解
x=x1+b/r*t , y=y1-a/r*t ,其中 t 为整数

  那里
b/r 与 a/r 为最小的周到,所以求得的解是最多最完善的

         又因 a%b=a-a/b*b

                与原命题争辨,则 y 与
x-py 互质

         当 b!=0 时,

         设
ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2

 

 

                设 y=nk , x-py=mk , 且
k>1 (因为互质)

    此等式恒创建

壹 、欧几里得算法(重点是表明,对持续知识有用)

    得证

                将 y 带入可得

                x-pnk=mk

 

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

  引理:存在 x , y 使得
gcd(a,b)=ax+by

    得证

    将
x , y 带入方程得

  证明:

  证明:

 

    ax+by=c

 

 

 

  通解为 x=x1+b/r*t