前几天做一个解离散对数的题用到了 gmpy，它是 GMP 的 Python 封装，用来算大数。

这里记两笔。首先是大整数需要用 mpz 对象，例如：

p = mpz(13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)

判断大数是否是质数：is_prime(p) （求离散对数其实用不着）

求逆元 $x^{-1}$：invert(x, p)。例如， y = invert(x, p) 则 $(x * y) \mod p = 1$

幂取模：pow(x, n, p)，即 $x^n \mod p$。结果仍为 mpz。

mpz 对象可以直接用在 dict 中做键值。

题目中提供的方法是分治，将解 $x$ 拆成两部分 $x_0 * B + x_1$，其中$B$是2的整数次方幂（约为$x$上限的开方，例如，如果$x$的范围是$2^{40}$，则$B=2^{20}$。这样 $x_0$, $x_1$ 分别小于 $B$，将方程整理成 $x_0$, $x_1$ 分别在等式左右（其它部分都是常数了），然后穷举 $x_0$ 对应的值（计算$2^{20}$次，保存所有结果），然后穷举所有的 $x_1$ 对应的值，如果发现之前保存的结果中有匹配，则输出对应的 $x_0$, $x_1$，从而算出 $x$。由于将搜索范围变成了 $\sqrt{N}$，所需的时间也就大大减少了。