数论是 CSP-S 的重要考点。本文梳理常用的数论知识。

常见数论知识

1. 素数

  • 判定：试除法 O(sqrt(n))
  • 筛法：埃氏筛、欧拉筛

2. 最大公约数 / 最小公倍数

  • GCD：辗转相除法
  • LCM：a*b/gcd(a,b)

3. 快速幂

  • 计算 a^n mod m
  • O(log n) 复杂度

咨询数论学习：151 6522 2880