本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-04 09:42:27

同余：a和b除以p的余数相同，记作 $a\equiv b\pmod{p}$。

模运算：

1. $（a+b) \mod p=((a\mod p) + (b \mod p)) \mod p$

2. $a \times b \mod p =(a \mod p) \times (b \mod p) \mod p$

3. 若 $a\equiv b\pmod{p}$，$b\equiv c\pmod{p}$，则$a\equiv c\pmod{p}$。

费马小定理：若p为质数，则$a^p \equiv a \pmod{p}$

当a不是p的倍数时，$a^{p-1} \equiv 1 \pmod{p}$

埃氏筛复杂度：$O(n\log \log (n))$

Pollard_Rho 算法(未写完）

生成一个随机序列a，若 $\gcd(\left\ert a_i-a_{i-1}\right\ert)$