裴蜀定理与扩展欧几里得算法

发表于 | 分类于

扩展欧几里得算法用于求裴蜀方程$ax+by=gcd(a,b)$的一组解，该算法基于裴蜀定理与欧几里得算法。

裴蜀定理

  • 内容

    对于整数$a,b,m$，裴蜀等式$ax+by=m$有解的充要条件为：$m$是$a,b$最大公因数的整数倍。当等式有解时，解有无穷多组。

  • 证明

    \[\begin{aligned} &若a=0或b=0：假设b=0，即求ax=m。此时gcd(a,b)=a，当方程有解时显然m为a的整数倍。\\ &当a,b都不为零时：令A=\{ax+by|<x,y>\in Z^{2} \},因为|a|,|b|\in A，所以A\cap N^*\neq \emptyset 。\\ &令\:d_0=ax_0+by_0为A中的最小正元素。任取正元素p=ax_1+by_1\in A，设\:p=kd_0+r，0\leq r< d_0 \\ &有\:r=ax_1+by_1-k(ax_0+by_0)=a(x_1-kx_0)+b(y_1-ky_0)\in A\\ &所以\:r=0，所以d_0|p，所以A中任何元素都是d_0的整数倍(p<0时，把p大于零的情况中的x，y取相反数)\\ &对于a,b的任意一个公因数d，有d_0=akd+bld，所以d|d_0，这就证明了d_0=gcd(a,b)。\\ &综上，方程ax+by=m,m=m_0d_0的解可以表示成\\ &\{(m_0x_0+\frac{kb}{d_0},\:m_0y_0-\frac{ka}{d_0})|k\in Z\}\\ &证毕 \end{aligned}\]

  • 拓展

    $a_1,a_2…a_n$是一组正整数，d是他们的最大公因数，那么存在一组正整数$x_1,x_2…x_n$使得$a_1x_1+a_2x_2…a_nx_n=d$

扩展欧几里得算法

  • 简介

    扩展欧几里得算法可以求出方程$ax+by=gcd(a,b)$的一组解，并且在求出一组解的同时得到a,b的最大公因数。

  • 原理

    \[\begin{aligned} &设\:ax_0+by_0=gcd(a,b)\\ &\quad bx_1+a\,mod\,b\,y_1=gcd(b,a\,mod\,b)\\ &由欧几里得算法可知：\\ &\begin{aligned} ax_0+by_0&=bx_1+a\,mod\,b\,y_1\\ &=bx_1+(a-b[\frac{a}{b}])y_1\\ &=ay_1+b(x_1-[\frac{a}{b}]y_1) \end{aligned}\\ &令x_0=y_1,y_0=x_1-[\frac{a}{b}]y_1\\ \end{aligned}\]

于是就可以用类似欧几里得算法中的递归做法运算，直到y前的系数为0(此时等式右边的常数就是$a,b$的最大公因数)，之后再回代得到一组$(x_0,y_0)$的解。

  • 代码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    ll exgcd(ll a, ll b, ll &x, ll &y){
  if(!b){
      x = 1;
      y = 0;
      return a;
  }
  int d = exgcd(b, a%b, x, y);
  int t = x;
  x = y;
  y = t-a/b*y;
  return d;
}

应用

  • 运用扩展欧几里得算法可以求出同余方程$ax\equiv1(mod\,b)$的最小整数解，即求解$ax+by=1$。所求得的最小整数解实际上就是a的逆元。

    题目链接P1082 [NOIP2012 提高组] 同余方程

  • gym/100963 J

    这个题实际上是求解$ax+by=c$，并且要使x为最小非负整数解，并且y不为正。只需要令等式右边的常数为负，求解出一组解后根据裴蜀定理解集表示的结论来求出x的最小非负整数解。这样就能满足x是所需要的答案，因为当x为非负，c为非正时，y一定非正。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    #define LOCAL
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define debug(msg) cout << (msg) << endl
#define FOR(i, a, b) for (int i=a; i<=(b); i++)
#define pb(x) push_back(x) 
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define JUDGE(x) if(x) cout << "Yes\n"; else cout << "No\n";
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y){
  if(!b){
    x = 1;
    y = 0;
    return a;
  }
  int d = exgcd(b, a%b, x, y);
  int t = x;
  x = y;
  y = t-a/b*y;
  return d;
}
ll gcd(ll a, ll b){
  return b==0?a:gcd(b, a%b);
}
int main()
{
  #ifdef LOCAL
    freopen("in.txt", "r", stdin);
      freopen("out.txt", "w", stdout);
  #endif
  ll m, n, a, k;
  while(cin >> n >> m >> k >> a){
    if(!(a||k||m||n)) break;
    a += k;
    if(a>n){
      swap(a, n);
      swap(k, m);
    }
    ll x, y;
    ll d = exgcd(m, k, x, y);
    if((a-n)%d){
      cout << "Impossible\n";
      continue;
    }
    ll t = (a-n)/d;
    x *= t;
    x %= k/d;
    x = x+(k/d);
    x %= k/d;
    cout << x*m+n << endl;
  }
  return 0;
}