红魔咖啡馆

红魔咖啡馆

头发越掉越多，头发越掉越少

1. 裴蜀定理

裴蜀定理

内容

若a和b是不全为0的整数，则有整数x、y使得

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

推论

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

扩展欧几里得算法

对于方程，当a和b确定，那么也确定，保证入参a和b没有负数

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

// 扩展欧几里得算法
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;
}

时间复杂度：理论，实际

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可