数论的乱七八糟杂碎

没什么营养价值

Posted by Ghastlcon on January 8, 2019
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 数论的乱七八糟杂碎

越靠前的大概越重要。

  • 若 $a\perp p$,则 $a^{\varphi(p)}\equiv 1 \pmod p$
  • $a^x\equiv b \pmod p\;(p\neq 1)$ 无解当且仅当不满足 $\gcd(a,\,p)\;|\;b$
  • 若 $a\equiv b\pmod p$,且 $\gcd(a,\,p)\;|\;b$,则 $\frac{a}{\gcd(a,\,p)}\equiv \frac{b}{\gcd(a,\,p)}\pmod {\frac{p}{\gcd(a,\,p)}}$
  • $a^k=\begin{cases}a^k & \text{if } k\leq \varphi(p) \\ a^{k\operatorname{mod}\varphi(p)+\varphi(p)} & \text{otherwise} \end{cases}$
  • $\varphi(n)=n\prod_{i=0}^k\frac{p_i-1}{p_i}$,总是记不住
    1. $ID=\varphi\otimes I$,$e=\mu \otimes I$,$\varphi=\mu \otimes ID$
    2. $\sigma_0=I\otimes I$,$\sigma_1=ID\otimes I$
    3. 以上可以套出很多奇怪的东西,比如 $\sigma_1=\varphi\otimes \sigma_0$
  • 反演可以把枚举因数变成枚举倍数,经常有意想不到的效果
  • 阶乘取模直接分块打表,不要去写 $\text{min_25}$ 之类烦人东西
  • $a^{-1}\pmod p=(p-\lfloor\frac{p}{a}\rfloor)\cdot(p\operatorname{mod}a)^{-1}\pmod p$
  • $a$ 在模 $p$ 剩余系下有逆元当且仅当 $a\perp p$,费马小定理只能在 $p\in \mathbb{P}$ 时使用


如果本文帮助到了你,希望你能撰写评论,非常感谢 $\text{w}$