ExGCD

概念

对于不完全为0的非负整数$a,b$，必然存在整数对$x,y$，使得$gcd(a,b)=ax+by$。

代码

typedef long long LL;
LL ans;
LL exgcd (LL a,LL b,LL &x,LL &y)
{
    if (!b) { x=1,y=0; return a; }
    LL t=exgcd (b,a%b,y,x);
    y-=a/b*x;
    return t;
}

栗1

LuoguP1082
移动$\%b$到左边，得$ax\%b=1$，设$y$，则$ax+by=1$.
若$gcd(a,b)|1$，则有解。（虽然数据保证有解）

栗2

LuoguP1516
解方程：$x+km\equiv y+kn\pmod{l}$，求$k$
变化一下：$x+km-(y+kn)=zl,z \in Z$
设 $S=x-y,W=n-m$（有变号）
则：$kW+zl=S$
先$Exgcd$，求出一组特解。
由于求的时候，解的是$k_jW+z_jl=gcd(W,l)$
$k_j$位方程的一个特解。
之后，这个方程的所有解就可以表示成:$k_i=k_j+t\frac{l}{gcd(W,l)}$
想要通过一个特解推出最小解，可以：
$k_{min}=k_j$ $~$ $mod $ $~$ $\frac{l}{gcd(W,l)}$
因为 $k$ 建立在 $exgcd$ 得出的方程上，方程右边是 $gcd(W,l)$ 而不是$S$,所以将结果 $\times{ \frac{S}{gcd(W,l)} }$
（%%%_pks ‘w&皎月半洒花）

总结

将不定方程转化为可用$Exgcd$解决的形式。

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：ExGCD”

• ← Previous Post
• Next Post →