例题：Luogu P5435

预处理 GCD

一种 预处理， 查询两个小于 的数的快速 。

引理

对于任意正整数 ，可以将 写成 ，满足 任意一个小于 或为质数。

考虑归纳，首先对于 ，显然成立。

否则，设 的最小质因子为 ，设 是一个合法表示，不妨设 。若 ，则 是一个合法表示。不然有 ，则 。若 ，有 ，则 ，矛盾，因此 是合法表示。

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

预处理

• 预处理所有 ，其中 的 。显然可以 推出来。
• 预处理 以内质数。

查询

计算 。

设 ，则：

若 ，只需判断 是否整除 ，否则 ，因为 ，可以查表。

实现

const int T = 1000;
const int M = 1000000;

int g[T][T], fac[M][3];
bitset<M> vis;
vector<int> pri;
void prework() {
  vis[0] = vis[1] = true;
  fac[1][0] = fac[1][1] = fac[1][2] = 1;
  for (int i = 2; i < M; ++i) {
    if (!vis[i]) {
      fac[i][0] = fac[i][1] = 1;
      fac[i][2] = i;
      pri.push_back(i);
    }
    for (int j : pri) {
      int mul = i * j;
      vis[mul] = true;
      fac[mul][0] = fac[i][0] * j;
      fac[mul][1] = fac[i][1];
      fac[mul][2] = fac[i][2];
      sort(fac[mul], fac[mul] + 3);
      if (i % j == 0)
        break;
    }
  }
  for (int i = 0; i < T; ++i)
    g[0][i] = g[i][0] = i;
  for (int i = 1; i < T; ++i)
    for (int j = 1; j <= i; ++j)
      g[i][j] = g[j][i] = g[j][i % j];
}
int gcd(int a, int b) {
  int ans = 1;
  for (int i = 0; i < 3; ++i) {
    int _ = fac[a][i] > T ? (b % fac[a][i] ? 1 : fac[a][i])
                          : g[fac[a][i]][b % fac[a][i]];
    b /= _;
    ans *= _;
  }
  return ans;
}

更相减损术

小常数 。

• 若 ，
• 若 ，。
• 若 （反之同理），。
• 若以上均不满足，设 ，则 。

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;
}