程序代码来自redcastle,我看了很多的关于一元同余方程的解释,都不是很名白,今天在redcastle的博客上看到了他的解释恍然大悟,终于把1061给AC了,是代码,

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

由题意可知:y+nt-(x+mt)=dL ————> y-x=dL+(m-n)t

关于一元同余方程的解释。

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

则此方程可用扩展欧几里得算法求解

 

证明:

因为ax+by=d的答案不唯一,当x增加b,y减少a,和不变。

 

       a可以表示成a = kb + r,则r = a mod b

/************************/

我还是把我代码写出来

  假设d是a,b的一个公约数,则有

转帖一个关于扩展欧几里得算法的讲解

 

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

扩展欧几里得算法——求解线性方程ax+by=c

 

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

1.应用:
      线性方程ax+by=c ,已知a,b,c,求解x,y.

#include <iostream>
using namespace std;
struct strple
{
 int x,y,r;
};
__int64 mod(__int64 a,__int64 b)
{
return (a%b+b)%b;
}
int Euild(int a, int b)
{
 if(b==0)
  return a;
 else
  return Euild(b,mod(a,b));
}
strple Extrend_Euild(__int64 a,__int64 b)
{
 strple result;
 if(b==0)
 {
  result.x=1;
  result.y=0;
  result.r=a;
 }
 else{
  strple ee=Extrend_Euild(b,mod(a,b));
  result.x=ee.y;
  result.y=ee.x-(a/b)*ee.y;
  result.r=ee.r;
 }
 return result;
}
__int64 MLES(__int64 a,__int64 b, __int64 n)
{
 strple ee=Extrend_Euild(a,n);
 if(mod(b,ee.r)==0)
  return mod(ee.x*(b/ee.r),n/ee.r);
 else
  return -1;
}
int main()
{
 __int64 x,y,m,n,l;
 while(scanf(“%I64d%I64d%I64d%I64d%I64d”,&x,&y,&m,&n,&l)!=EOF)
 {
 __int64 mles;
 mles=MLES(m-n,y-x,l);
 if(mles<0)
  cout<<“Impossible”<<endl;
 else
  printf(“%I64dn”,mles);
 }
 return 0;
}

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

2.基本思路:
    
      ax+by=c有解 =>
c=k*gcd(a,b)=kd(因为d=gcd(a,b)=>d|(ax+by))
      
      我们先考虑求解  ax+by=d
        由欧几里得算法,d=bx’+(a mod
b)y’=bx’+(a-[a/b]b)y’=ay’+b(x’-[a/b])y’    
        则由上述两式子,我们可以得出 x=y’ ,y=x’-[a/b]y’
       
这样子,在欧几里得算法添加x,y变量,最后得到解。(可结合下面代码源代码进行理解)

 

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

      接下来我们来看看ax’+by’=d和ax+by=c之间的关系
      
        (c/d)ax’+(c/d)by’=(c/d)d 即 可以得到 x=(c/d)x’,y=(c/d)y’
         
         所以可以得到ax+by的一组解
         那么ax+by=c所有解的形式是什么呢?
             a(x+qb)+b(y-qa)=c; q为任意整数
(注意,当要求y-qa的最小正整数min时,由y-qa>=0,
q取[y/a]最小,min=y-[y/a]y,但是,[y/a]可能为0,如果y是负数,min此时也为负数,不好,此时令min+=a就可以取得最小正整数值了([y/a]=0所以|y|<a),这段可以自己找个例子好好理解下啊)

 

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

3.源代码模板

  因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

int Extended_Euclid(int a,int b,int& x,int &y)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int d=Extended_Euclid(b,a%b,x,y);
    int temp=x;x=y;y=temp-a/b*y;
    return d;
}
//用扩展欧几里得算法解线性方程ax+by=c;
bool linearEquation(int a,int b,int c,int& x,int &y)
{
    int d=Extended_Euclid(a,b,x,y);
    if(c%d) return false;

算法实现:

    int k=c/d;
    x*=k;y*=k;//求的只是其中一个解
    return true;
}

 

 

 

注意,其中扩展欧几里得算法的返回值还是gcd,

  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. }  

/************************/

二   扩展欧几里得算法:

AC代码如下:

 

澳门新葡萄京官网首页 1澳门新葡萄京官网首页 2代码

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

 1 #include <stdio.h>
 2 long long  mod(long long a,long long  b)
 3 {
 4     return (a%b+b)%b;
 5 }
 6 long long exten_gcd(long a,long b,long long *x,long long *y)
 7 {
 8     long long r,t;
 9     if (b==0)     
10     {
11         r=a;*x=1;*y=0;
12     }
13     else 
14     {
15         r=exten_gcd(b,mod(a,b),x,y);
16         t=*x;*x=*y;*y=t-(a/b)**y;
17     }
18     return r;
19 }
20 main()
21 {
22     long x,y,m,n,l;
23     long long rx,ry,t,d;
24     scanf(“%d%d%d%d%d”,&x,&y,&m,&n,&l);    
25     d=exten_gcd(m-n,l,&rx,&ry);
26     if (mod(y-x,d)) printf(“Impossiblen”);
27     else
28     {
29         rx*=(y-x)/d;
30         printf(“%lldn”,mod(rx,l));
31     }
32     return 0;
33 }
34 

 

 

   证明:设 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);

  根据朴素的欧几里德原理有 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,所以递归可以结束。

     

 

  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;  

刘汝佳的:

 

 

  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. }  

上面求出的 x(当a>b时)都是最接近0的正整数。(不知道为什么)

 

 

扩展欧几里德算法的应用主要有以下两个方面:

(1)求解不定方程;

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

 

 

(1)求解不定方程;

  1.对于不定整数方程ax+by=m,若 m mod 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;

上面已经列出找一个整数解的方法,在找到 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为任意整数);
证明:

     
令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上。

代码:

 

 

  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. }  

相关题目:poj2115 poj2142 poj1061。

 

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

        同余方程 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’, 如果d |
b, 则方程ax = b(mod n)有一个解的值为x0, 满足:、

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

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

  有了这两个定理, 解方程就不难了。

代码:

 

  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(“%dn”, (x0 + i*(n/d))%n);  
  10.     return true;  
  11. }  

 

相关题目  hdu1576.

同余方程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
为整数。这个可用扩展欧几里德算法求出,原同余方程的唯一解就是用扩展欧几里德算法得出的
x 。

代码:

 

  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. }  

相关题目: hdu2115.