一百个大数分解质因数
场景：~/work/nt/factor.cpp 分解质因数，结果对，可遇到 10^10 级的大素数就要跑很久。 任务：改写 factorize，让 100 个 10^10 以内的数在 2 秒内分解完，输出格式不变。make 编译（-O2）后
模意义下的除法
第 1 步：下面是 3·x 除以 7 的余数 第 2 步：3×1 模 7 余 3，不是 1 第 3 步：3×2 模 7 余 6，不是 1 第 4 步：3×3 模 7 余 2，不是 1 第 5 步：3×4 模 7 余 5，不是 1 第 6 步
逆元的定义
a 关于模 p 的逆元 x，满足 a·x 除以 p 的余数是【0】。
逆元什么时候存在
a 关于模 p 的逆元存在，当且仅当【0】。
费马小定理说什么
p 是质数、a 不是 p 的倍数时，费马小定理说 a^(p-1) ≡【0】(mod p)。
为什么不能直接整数除
在「模 p 计数」里不能直接用整数除法 /，因为【0】。
试出 3 的逆元
C++ 没有 Python 那种 pow(3, -1, 7)，先用最笨的办法挨个试： #include <array> #include <iostream> #include <string> #inc
exgcd 求的是什么
第 1 步：递归：(30, 12) 第 2 步：递归：(12, 6) 第 3 步：递归：(6, 0) 第 4 步：b 为 0：x=1，y=0 第 5 步：回代：x=下一层 y，y=… 第 6 步：回代：x=下一层 y，y=… 第 7 步：3
exgcd 的递归边界
exgcd 递归到 b == 0 时 x = 1，y =【0】。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y；inv_ex(a, p) 用它求逆元。
exgcd 能顺带求什么
用 exgcd 可以直接求出【0】。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y；inv_ex(a, p) 用它求逆元。