同余

同余式性质


$a\equiv b \pmod{m}$

  1. 反身性 $a \equiv a \pmod {m}$
  2. 对称性 $a \equiv b \pmod {m}$ $\Rightarrow$ $ b \equiv a \pmod {m}$
  3. 传递性 $a \equiv b \pmod {m}$,$b \equiv c \pmod {m}$ $\Rightarrow$ $a \equiv c \pmod {m}$
  4. 相加 $a \equiv b \pmod {m}$,$c \equiv d \pmod {m}$ $\Rightarrow$ $a \pm c \equiv b \pm d \pmod {m}$
  5. 相乘 $a \equiv b \pmod {m}$,$c \equiv d \pmod {m}$ $\Rightarrow$ $ac \equiv bd \pmod {m}$
  6. 除法 $ac \equiv bd \pmod {m}$ $\Rightarrow$ $a \equiv b \pmod { \frac{m}{(c,m)}}$
  7. 乘幂 $a \equiv b \pmod {m}$ $\Rightarrow$ $a^n \equiv b^n \pmod {m}$


剩余系


完全剩余系:模$n$意义下的完全剩余系$Z_n=${$0,1,…n-1$},每个元素代表一个同余等价类
缩系:模$n$意义下的缩系$Z_n*=${$x|x \in Z_n,(x,n)=1$}

模m意义下乘法群逆元

$ax\equiv 1 \pmod{m}$

$(a,m)=1 \Rightarrow x$存在

性质

  1. 存在唯一性
  2. 完全积性函数
  3. $a/b\equiv a\times inv(b) \pmod{m}$

Calc

Euler theorem

若正整数$a$、$m$互质

$a^{\varphi (m)} \equiv 1 \pmod {m}$

Fermat’s little theorem

若正整数$a$、$m$互质且$m$为质数

$a^{m-1} \equiv 1 \pmod {m}$

EX Euclid algorithm

根据定义求解同余方程

线性递推

$inv(i) \equiv (m-\frac{m}{i})\times inv(m \% i) \pmod{m}$

推导与证明


同余方程

方程组

CRT

两两合并

模意义下的运算


常见运算取模

$+、-、\times、\div、$^

$a +b \equiv((a \mod m)+(b \mod m)) \pmod {m}$

$a -b \equiv((a \mod m)-(b \mod m)+m)\pmod {m}$

$ab \equiv ((a\mod m)(b \mod m))\pmod {m}$


$a/b \mod m$

$Case1:a|b$

if((b,m)=1) 乘法逆元求解
else $a/b \equiv (a\% bm)/b \pmod{m}$

$Case2:!(a|b)$

$c=a \% b,a/b \equiv ((a-c)\% bm)/b\pmod{m}$


$a^b \mod m$

$Case1:$减小a

$Case2:$减小b

(EX Euler theorem)

组合数取模

$C_{n}^{m} \mod P$

$Case1:$$n,m \leq 1000,P \leq 10^9$

杨辉三角递推求解

$Case2:$$n,m \leq 10^6$

分解质因数/预处理逆元和逆元的阶乘根据定义计算

$Case3:$$n,m \leq 10^{18},P \leq 10^5$

if P is a Prime

Lucas定理

$C(n,m) \equiv C(n\% P,m \% P) \times C(n/P,m/P)$

if P is not a Prime

EX Lucas 定理

对$P$进行质因数分解,对每个质因子得到一个同余方程,使用$CRT$合并

现在需要求$C_{n}^{m} \% p_i^{e_i}$,也即$n! \% p_i^{e_i}$

分三部分求解

  1. $p_i$的幂,直接求解
  2. 一个新的阶乘,递归求解
  3. 剩下的暴力求解
笔记 推导与证明

高次剩余

阶、原根、指标

离散对数BSGS

EXBSGS

模质数二次剩余的 Cipolla 算法

分享到: