O(1)黑科技

@CYJian 出了一道黑科技二合一,我就顺便跟着学了学。

O(1) gcd

在 O(V) 的预处理后可以做到 O(1) 查询 gcd ,其中 V 是权值的大小。

主要利用到的一个性质是可以将任意 x 分解为三个数 a * b * c , a, b, c 分别满足以下两个条件之一:

  1. 不超过 \(\sqrt{x}\)
  2. 是质数。

update: 之前写假了,感谢 @CYJian 的 hack 。

zzq 把满足这个性质的分解称为“迷之分解”,那我也这么叫吧。

考虑证明一下,顺便构造一个“迷之分解”。

找到 x 的最小质因子 p ,然后假设已知 x / p 的“迷之分解” A, B, C (A <= B <= C) 。
那么把 p 乘到 A 上就可以得到 x 的“迷之分解” A * p, B, C 。
分类讨论,如果 p 不超过 \(\sqrt[4]{x}\) ,由于 A 是 A, B, C 三者中最小的,
一定满足 A 不超过 \(\sqrt[3]{x/p}\) ,那么可得:

\[A \cdot p \leq \sqrt[3]{x/p} \cdot p = \sqrt[3]{xp^2} \leq \sqrt{x}\]

而如果 p 超过 \(\sqrt[4]{x}\) ,由于 p 是最小质因子,
那么如果 x 的“迷之分解”有合数 C , C 至少是 \(p^2\) ,超过 \(\sqrt{x}\)
那么 B 的大小就会比 p 小,与 p 是最小质因子矛盾,
因而此时 x 的“迷之分解”全是质数。

“迷之分解”的分析就是这样,通过线性筛可以很好预处理出 O(V) 内的所有数的“迷之分解”。
只需筛出每个数的最小质因子即可按上述方法递推出“迷之分解”。
然后只需预处理出 \(O(\sqrt{V})\) 内两两的 gcd ,为了不带 log ,需要递推预处理。
此时求 gcd(x, y) 只需对于 x 的“迷之分解” A, B, C 依次对 y 求 gcd (每次求 gcd 后把 y 除以该 gcd ),
以 A 为例,如果 A 不超过 \(\sqrt{x}\) ,直接查表可以得到 gcd(A, y) (查的是 gcd(A mod y, A) ),
否则 A 为质数,简单讨论一下就可以得到 gcd(A, y) 了。

关键部分参考实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int magic[maxv][3]; // 每个数的“迷之分解”
int gcd[maxb][maxb]; // 预处理的 gcd
int GCD(int x, int y) {
int res = 1;
for(int i = 0; i < 3; i ++) {
int X = magic[x][i];
int d;
if(X < maxb)
d = gcd[X][y % X];
else if(y % X)
d = 1;
else
d = X;
res *= d;
y /= d;
}
return res;
}

O(1) 快速幂

\(O(\sqrt{p})\) 的预处理后可以做到对于一个固定的底数 O(1) 查询快速幂,
其中 p 是模数(或者上式是 \(\sqrt{\phi(p)}\) ),或者是指数的范围。

这个就简单得多,对于每个 \(a^k\) 的指数 k 都可以表示为 \(a \sqrt{p} + b\) 的形式,
满足 \(a, b < \sqrt{p}\) ,分别预处理即可,
即预处理 \(a^0, a^1, a^2 ... a^{\sqrt{p}}, a^{2\sqrt{p}}, a^{3\sqrt{p}} ... a^p\)