5.4 杂记

· · 算法·理论

同余：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\vert a_i-a_{i-1}\right\vert)