欧几里得

数学

一、$gcd(a,b)=gcd(b,a\%b)$

证明：

令 $a=kb+r$ 所以 $r=a\%b$
令 $d$ 为 $a,b$ 的公因数
则 $r/d=(a-kb)/d$ 为整数
所以 $a,b$ 的公因数也是 $r$ 的因数，得证

二、拓展欧几里得

求解$Ax+By=C$的问题
1、若$C\%gcd(A,B)!=0$则无解
2、$Gcd=gcd(A,B);A/=Gcd,B/=Gcd,C/=Gcd$
3、代入下面代码求$Ax+By=1$
4、$x*C$，得到一组特解
5、通解为$\begin{cases}x=x_0+k*B \\y=y_0+k*A\end{cases}$

void Exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return;}
    ll x1,y1;Exgcd(b,a%b,x1,y1);
    x=y1;y=x1-a/b*y1;
}

三、题目

练习题

• P1082 同余方程 https://www.luogu.org/problemnew/show/1082
• P1516 青蛙的约会 https://www.luogu.org/problemnew/show/P1516

考试题

• 2017.12.27 CodePlus T1 矩阵乘法+EXGCD