数学
数学定理
1.费马小定理
若 \(p\) 为质数，且 \(p \nmid a\)，有 \(a^{p - 1} \equiv 1 \pmod{p}\)，不给证明，只记结论。
-
那么 \(\frac{x}{a}\) 在模 \(p\) 意义下为 \(\frac{x}{a} \equiv \frac{x}{a} \cdot a^{p - 1} \equiv x \cdot a^{p - 2} \pmod{p}\)
-
\(a\) 在模 \(p\) 意义下的乘法逆元为 \(a^{p - 2}\) （\(p\) 为质数，\(p \nmid a\)）
记作：\(a^{-1} = a^{p-2} \pmod{p}\)
2.位运算的一个定理
\(x + y = 2(x \And y) + (x \oplus y)\)
\(x \mid y = (x \And y) + (x \oplus y)\)