欧几里得算法

简述

首先说一下欧几里得算法怎么回事
gcd(a,b)=gcd(b,a%b)这就是欧几里得算法
然后还需要记住一个结论
gcd(a,b)与gcd(a+bt,b)互质属性相同，也就是a,b互质那么a+bt与b也互质其中t是一个任意的整数

代码

int gcd(int a,int b)
{
  return !b?0:gcd(b,a%b);
}

拓展欧几里得算法

简述

首先说一下线性同余方程ax≡c(mod b)是什么意思？
线性同余顾名思义就是左边与右边余数相同也就是说(ax)%b=c%b
也就是说(ax-c)%b=0
也就是说(ax-c)=by
所以
ax+by=m
这也就是一个二元一次方程
因为只有一个式子所以他的解是无穷多个的
拓展欧几里得算法算的就是ax+by=gcd(a,b)时候的x和y是多少
说是拓展欧几里得算法，那么其中肯定包含求gcd的一般欧几里得算法

代码

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

唯一需要记忆的地方就是y-=x*(a/b);
其中d是gcd(a,b) x,y是求解的值

拓展

这样我们把特殊的ax+by=gcd(a,b)拓展到ax+by=c
那么我们就可以得到如果c|gcd(a,b)那么存在整数解否则不存在整数解
这样我们还需要知道一个延伸的最小整数解的公式为:
x0=(x0*(c/d))%b这里先c/d比较好保证不要爆表
b1=b/d
x=(x0%b1+b1)%b1