数论

\(gcd\) & \(exgcd\)

gcd

\[\gcd(a,b)=\gcd(b,a mod b)\]

这个结论还是比较显然的

给出代码:

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

---

exgcd

什么是exgcd呢----

就是解
\[ ax+by=\gcd(a,b)\]
这样的方程

那么怎么解呢?

首先有一个非常显然的结论

\[ax+by=\gcd(a,b)\]
\[bx+(a \bmod b)y=\gcd(b,a \bmod b)\]

是同解的
那么可以递归求到解集

我们给出边界条件
\[ax+by=\gcd(a,b) (a=1,b=0)\]
时有\(x=1,y=0\)为其边界解