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)$

{\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](https://en.wikipedia.org/wiki/Divisibility_sequence). Same [for Fibonacci numbers.](https://math.stackexchange.com/a/60353/242) --- **Alternatively** it has a natural proof via the [Order Theorem](https://math.stackexchange.com/a/127118/242) $\ 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](https://math.stackexchange.com/a/88411/242) $\ 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][1] for more on this and the more familiar additive form of a **denominator ideal.** [1]:https://math.stackexchange.com/questions/4713/if-the-order-divides-a-prime-p-then-the-order-is-p-or-1/4715#4715 [2]:https://math.stackexchange.com/questions/7473/number-theory-proving-question/7561#7561 [3]:https://math.stackexchange.com/questions/7473/number-theory-proving-question/7479#7479