易叉 GCD

· · 算法·理论

OI Wiki

我根本不会呃阿基米德。

\gcd(a,b)=\gcd(b,a\bmod b)

证明：设 a=kb+c，即 c=a\bmod b。若 g\mid a 且 g\mid b，则 \displaystyle\frac{a}{g}=k\frac{b}{g}+\frac{c}{g}，可以得出 c 为 g 的倍数，也就是说 a 和 b 的因数一定也是 c 的因数，于是的证。

我根本就不会易叉 GCD。

需要解 ax+by=c 的正整数解。首先需要有 \gcd(a,b)\mid c。并且 ax+by=\gcd(a,b) 一定有可行正整数解。

证明：

记 g=\gcd(a,b)，首先 ax+by 一定是 g 的倍数。再考虑由偶记立德得到

ax+by=\gcd(b,a\bmod b)

考虑递归，假设对于下面方程有解

bx'+(a\bmod b)y'=\gcd(b,a\bmod b)

则有

bx'+\left(a-\left\lfloor\frac{a}{b}\right\rfloor\times b\right)y'&=g\\ ay'+b\left(x'+\left\lfloor\frac{a}{b}\right\rfloor\times y'\right)&=g \end{aligned}