5.4 杂记

__S08577__ · 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
   1. a \times b \mod p =(a \mod p) \times (b \mod p) \mod p

   2. 若 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\vert a_i-a_{i-1}\right\vert)