除零扩域

· · 算法·理论

某些计数题要求计算 \frac{x}{y} \bmod p,其中 p 是大质数。若 y 是 p 的倍数则逆元无定义,直接计算会爆掉。

将非零整数写成 a \times 0^b 的形式,其中 a \in \mathbb{Z}_p\setminus \{0\},b \in \mathbb{Z}。规定 0^0=1。这里的 0 本质上是 p。

记 S=\{a \times 0^b \mid a \in \mathbb{Z}_p\setminus\{0\}, b \in \mathbb{Z}\}。则 S 上的乘除有良定义:

这表明 \mathbf{(S ,\times )} 构成 Abel 群。

一般地,若最终答案满足 b=0,提取 a 输出即可,若 b>0,则答案为 0。

从高观点来看,这个 trick 本质上是在计算 p 进数域 \mathbb{Q}_p 中元素的 p 进估值 v_p(n) 以及最低位系数。

若将 0 视作形式元 x,其乘除法的代数结构同构于形式 Laurent 级数域 \mathbb{F}_p((x)) 的单项式乘除。