快速 GCD

预处理 GCD

\(O(n)\) 预处理，\(O(1)\) 查询两个小于 \(n\) 的数的快速 \(\gcd\)。

引理

对于任意正整数 \(n\)，可以将 \(n\) 写成 \(n=abc\)，满足 \(a,b,c\) 任意一个小于 \(\sqrt{n}\) 或为质数。

考虑归纳，首先对于 \(1\)，显然成立。

否则，设 \(n\) 的最小质因子为 \(p\)，设 \(\dfrac{n}{p}=xyz\) 是一个合法表示，不妨设 \(x\le y\le z\)。若 \(x=1\)，则 \(n=pyz\) 是一个合法表示。不然有 \(p\le x\le y\le z\)，则 \(p^4\le n\)。若 \(xp\gt\sqrt{n}\)，有 \(yp\gt\sqrt{n},zp\gt\sqrt{n}\)，则 \(xyzp^3\gt n^{3/2}\)，矛盾，因此 \(n=(xp)yz\) 是合法表示。

注意这个证明给出了合法表示的构造方法。

预处理

• 预处理所有 \((i,j)\)，其中 \(i,j\le \sqrt{n}\) 的 \(\gcd\)。显然可以 \(O(n)\) 推出来。
• 预处理 \(n\) 以内质数。

查询

计算 \(\gcd(x,y)\)。

设 \(x=abc\)，则

若 \(a\in\mathbf{P}\)，只需判断 \(a\) 是否整除 \(y\)，否则 \((a,y)=(y\bmod a,a)\)，因为 \(a\le\sqrt{n}\)，可以查表。

更相减损术

小常数 \(O(\log n)\)。

• 若 \(a=b\)，\((a,b)=a=b\)
• 若 \(2\mid a,2\mid b\)，\((a,b)=\left(\dfrac{a}{2},\dfrac{b}{2}\right)\)。
• 若 \(2\mid a,2\nmid b\)（反之同理），\((a,b)=\left(\dfrac{a}{2},b\right)\)。
• 若以上均不满足，设 \(a>b\)，则 \((a,b)=(a-b,b)\)。

int gcd(int a, int b) {
  int i = __builtin_ctz(a);
  int j = __builtin_ctz(b);
  int k = min(i, j);
  int d;
  b >>= j;
  while (a) {
    a >>= i;
    d = b - a;
    i = __builtin_ctz(d);
    if (a < b) b = a;
    if (d < 0) a = -d;
    else a = d;
  }
  return b << k;
}