Quack 知道好多东西，把它们都做成 ppt。
inv_gcd 还可以用递推矩阵算。
void exgcd(int a, int b){
r[0] = a, r[1] = b;
int i = 2;
for ( ; r[i - 1]; i++) {
r[i] = r[i - 2] % r[i - 1];
q[i - 1] = r[i - 2] / r[i - 1];
}
d = r[i -= 2];
mat res(1, 0, 0, 1);
for (int j = i - 1; j; --j)
res.mul(mat(0, 1, 1, -q[j]));
s = res.get(1, 0); t = res.get(1, 1);
}
还有个 trick 叫 binary gcd。
int gcd(int a, int b){
if (a == b) return a;
if ((a & 1) && (b & 1)) return gcd(b, abs(a - b));
else if ((a & 1) && (!(b & 1))) return gcd(a, b >> 1);
else if ((!(a & 1)) && (b & 1)) return gcd(a >> 1, b);
else return gcd(a >> 1, b >> 1) << 1;
}
复杂度和正确性平凡吧，在写高精度 gcd 的时候可以考虑。接下来看一个典中典问题：
证明：$(a^n-1, a^m-1) = a^{(n, m)}-1$。
P.f.：不妨设 $n \leqslant m$，首先 $(a^n-1, a^m-1) = (a^n(a^{m-n}-1), a^n-1) = (a^{m-n}-1, a^n-1)$，一直迭代可以得到 $(a^n-1, a^m-1) = (a^{(n, m)}-1, a^{(n, m)}-1) = a^{(n, m)}-1$。
然后这个有个 more general 的版本，就是对于任意整数 $a, b$，满足 $(a, b) = 1$ 则有 $(a^n-b^n, a^m-b^m) = a^{(n, m)}-b^{(n, m)}$，证明是类似的。
但是如果说我们还有一个 more more general 的版本呢？
Theorem：若 $f_n$ 是一个整数序列，并满足 $f_0 = 0$，$f_{n} \equiv f_{n-m} \pmod {f_m},n > m$，有 $(f_n, f_m) = f_{(n, m)}$。
P.f.：考虑 induction，当 $n = m$，$n = 0$，$m = 0$ 时，上述命题为一个，一个一个一个，一个一个一个一个一个一个一个
什么栈什么溢什么出上还有一些 q-analog 的高论，不过我连上面的证明都还没看懂。引一下原 writer：
Mimic in expts a subtractive Euclidean algorithm $\rm\,(n,m) = (\color{#0a0}{n\!-\!m},m)$
$$\begin{align} \rm{e.g.}\ \ &\rm (f_5,f_2) = (f_3,f_2) = (f_1,f_2) = (f_1,f_1) = (f_1,\color{darkorange}{f_0})= f_1 = f_{\:\!(5,\,2)}\[.3em]
{\rm like}\ \ \ &(5,\ 2)\, =\:\! (3,\ 2)\, =\:\! (1,\ 2)\:\! =\:\! (1,\ 1)\:\! =\:\! (1,\ \color{darkorange}0)\:\! = 1,\ \ {\rm since}\end{align}\qquad$$
$\rm\ f_{\,n}\: :=\ a^n\!-\!1\ =\ a^{n-m} \: \color{#c00}{(a^m\!-\!1)} + \color{#0a0}{a^{n-m}\!-\!1},\,\ $ hence $\rm\:\ {f_{\,n}\! = \color{#0a0}{f_{\,n-m}}\! + k\ \color{#c00}{f_{\,m}}},\,\ k\in\mathbb Z,\:$ thus
Theorem $\: $ If $\rm\ f_{\, n}\: $ is an integer sequence with $\rm\ \color{darkorange}{f_{0} =\, 0},\: $ $\rm \:{ f_{\,n}\!\equiv \color{#0a0}{f_{\,n-m}}\ (mod\ \color{#c00}{f_{\,m})}}\ $ for all $\rm\: n > m,\ $ then $\rm\: (f_{\,n},f_{\,m})\ =\ f_{\,(n,\:m)}, \: $ where $\rm\ (i,\:j)\ $ denotes $\rm\ gcd(i,\:j).\:$
Proof $\ $ By induction on $\rm\:n + m\:$. The theorem is trivially true if $\rm\ n = m\ $ or $\rm\ n = \color{darkorange}0\ $ or $\rm\: m = \color{darkorange}0.\:$
So we may assume $\rm\:n > m > 0\:$.$\ $ Note $\rm\ (f_{\,n},f_{\,m}) = (\color{#0a0}{f_{\,n-m}},\color{#c00}{f_{\,m}})\ $ follows by $\rm\color{#90f}{Euclid}$ & hypothesis.
Since $\rm\ (n-m)+m \ <\ n+m,\ $ induction yields $\rm\, \ (f_{\,n-m},f_{\,m})\, =\, f_{\,(n-m,\:m)} =\, f_{\,(n,\:m)}.$
$\rm\color{#90f}{Euclid}\!:\ A\equiv a\pmod{\! m}\,\Rightarrow\ (A,m) = (a,m)\,$ is the reduction (descent) step used both above and in the Euclidean algorithm $\rm\: (A,m) = (A\bmod m,\,m),\, $ the special case $\,\rm f_{\:\!n} = n\,$ above.
This is a prototypical strong divisibility sequence. Same for Fibonacci numbers.
Alternatively it has a natural proof via the Order Theorem $\ a^k\equiv 1\iff {\rm ord}(a)\mid k,\,$ viz.
$$\begin{eqnarray}\ {\rm mod}\:\ d\!:\ a^M\!\equiv 1\equiv a^N&\!\iff\!& {\rm ord}(a)\ |\ M,N\!\color{#c00}\iff\! {\rm ord}(a)\ |\ (M,N)\!\iff\! \color{#0a0}{a^{(M,N)}\!\equiv 1}\[.2em]
{\rm i.e.}\ \ \ d\ |\ a^M\!-\!1,\:a^N\!-\!1\! &\!\iff\!\!&\ d\ |\ \color{#0a0}{a^{(M,N)}\!-\!1},\qquad\,\ {\rm where} \quad\! (M,N)\, :=\, \gcd(M,N)
\end{eqnarray}\ \ \ \ \ $$
Thus, by above $\, a^M\!-\!1,\:a^N\!-\!1\ $ and $\, a^{(M,N)}\!-\!1\ $ have the same set $\,S\,$ of common divisors $\,d,\, $ therefore they have the same greatest common divisor $\ (= \max\ S).$
Note We used the GCD universal property $\ a\mid b,c \color{#c00}\iff a\mid (b,c)\ $ [which is the definition of a gcd in more general rings]. Compare that with $\ a<b,c \!\iff\! a< \min(b,c),\, $ and, analogously, $\,\ a\subset b,c\iff a\subset b\cap c.\ $ Such universal "iff" characterizations enable quick and easy simultaneous proof of both directions.
The conceptual structure that lies at the heart of this simple proof is the ubiquitous order ideal. $\ $ See this answer for more on this and the more familiar additive form of a denominator ideal.