【数学】裴蜀定理

裴蜀定理

内容

若a和b是不全为0的整数，则有整数x、y使得\(ax+by=\gcd(a,b)\)

即a、b的最大公约数=ax+by，随意给定x、y能得到的最小正数差值

推论

• 如果a和b是不全为0的整数，a与b互质，当且仅当存在整数x、y，使得\(ax+by=1\)
• 如果a和b是不全为0的整数，并且\(ax+by=c\)有解，那么c一定是\(\gcd(a,b)\)的整数倍
• a和b两项的裴蜀定理可以推广到多项的情况

扩展欧几里得算法

对于方程\(ax+by=\gcd(a,b)\)，当a和b确定，那么\(\gcd(a,b)\)也确定，保证入参a和b没有负数

扩展欧几里得算法可以给出a和b的最大公约数d以及其中一个特解x和y

1
2
3
4
5
6
7
8
9

// 扩展欧几里得算法
void exgcd(ll a, ll b, ll &x, ll &y){
  if (b==0){
    x=1,y=0;
    return;
  }
  exgcd(b,a%b,y,x);
  y-=a/b*x;
}

时间复杂度：理论\(O(\log \min(a,b))\)，实际\(O((\log \min(a,b))^3)\)