- 一个整数 \(N\) 的约数上界为 \(2\sqrt{N}\) 。
- \(1 \sim N\) 每个数的约数个数的总和大约为 \(N \times logN\) 。
- 取模运算性质
- 若 \(\forall a,b \in \mathbb{N}\) ,则 \(\gcd (a,b) \times \operatorname{lcm} (a,b)=a \times b\) 。
- \(\gcd(a,b)\) 用符号记作 \((a,b)\) ,\(\operatorname{lcm}(a,b)\) 用符号记作 \([a,b]\) 。
- 特别地,有 \(\gcd(a,0)=a\) 。
- 九章算术·更相减损法
- 若 \(\forall a,b \in \mathbb{N},a \le b\) ,则 \(\gcd (a,b)= \gcd (a,b-a)= \gcd (b,b-a)\) 。
- 证明:设 \(d= \gcd(a,b),k_1= \frac{a}{d},k_2= \frac{b}{d}\) ,移项得 \(a=k_1 d,b=k_2 d\) ,又因为 \(d|(b-a),b-a=(k_2-k_1)d\) ,故 \(\gcd(a,b-a)= \gcd(k_1 d,(k_2-k_1)d)=d\) ,\(b\) 与 \(b-a\) 同理。
- 若 \(\forall a,b \in \mathbb{N}\) ,则 \(\gcd(2a,2b)= 2\gcd(a,b)\) 。
- 优化:luogu P2152 [SDOI2009] SuperGCD
- 若 \(\forall a,b \in \mathbb{N},a \le b\) ,则 \(\gcd (a,b)= \gcd (a,b-a)= \gcd (b,b-a)\) 。
- 欧几里得算法
- 若 \(\forall a,b \in \mathbb{N}\) ,则 \(\gcd(a,b)= \gcd(b,a \bmod b)\) 。
- 证明
- 若 \(a<b\) ,则 \(\gcd(b,a \bmod b)=\gcd(b,a)=\gcd(a,b)\) 。
- 若 \(a \ge b\) ,设 \(d= \gcd(a,b),a=q \times b+r(0 \le r <b)\) ,则 \(r=a \bmod b=a-q \times b\) ,又因为 \(d|a,d|b,d|(q \times b)\) ,则 \(d|(a-q \times b)\) ,即 \(d|r\) ,故 \(\gcd(a,b)=\gcd(b,r)=\gcd(b,a \bmod b)\) 。
- 证明
- 时间复杂度为 \(O(\log \max(a,b))\) 。
- 代码实现
int gcd(int a, int b) { return b?gcd(b,a%b):a; }
- 若 \(\forall a,b \in \mathbb{N}\) ,则 \(\gcd(a,b)= \gcd(b,a \bmod b)\) 。
- 扩展欧几里得算法
- 裴蜀定理(贝祖定理, \(Bézout\) 定理)
- 对于任意整数 \(a,b\) ,存在一对整数 \(x,y\) ,满足 \(ax+by= \gcd(a,b)\) 。
- 证明:
- 当 \(b=0\) 时,有一对整数 \(x=1,y=0\) 满足 \(a \times 1+0 \times 0= \gcd(a,0)\) 。
- 若 \(b>0\) ,则 \(\gcd(a,b)= \gcd(b,a \bmod b)\) 。假设存在一对整数 \(x,y\) ,满足 \(b \times x+(a \bmod b) \times y= \gcd(b,a \bmod b)\) ,又因为 \(b \times x+(a \bmod b) \times y=b \times x+(a-b \times \left\lfloor\dfrac{a}{b}\right\rfloor) \times y=a \times y+b \times (x-\left\lfloor\dfrac{a}{b}\right\rfloor \times y)\) ,所以令 \(x'=y,y'=x-\left\lfloor\dfrac{a}{b}\right\rfloor \times y\) ,此时有 \(ax'+by'= \gcd(a,b)\) 。
- 例题:luogu P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目
- 推广
- 对于任意整数 \(a_1,a_2,a_3,...a_n\) ,存在与之相对应的整数 \(x_1,x_2,x_3,...,x_n\) ,满足 \(a_1 x_1+a_2 x_2+a_3 x_3+...= \gcd(a_1,a_2,a_3,...,a_n)\) 。
- 例题:luogu P4549 【模板】裴蜀定理
- 证明:
- 对于任意整数 \(a,b\) ,存在一对整数 \(x,y\) ,满足 \(ax+by= \gcd(a,b)\) 。
- 代码实现
int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } else { int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } }
- 上述程序求出方程 \(ax+by= \gcd(a,b)\) 的一组特解 \(x_0,y_0\) ,并返回 \(a,b\) 的最大公因数 \(d\) 。
- \(x_0,y_0\) 是 \(ax+by= \gcd(a,b)\) 中 \(|x|+|y|\) 最小的整数解。
- 上述程序求出方程 \(ax+by= \gcd(a,b)\) 的一组特解 \(x_0,y_0\) ,并返回 \(a,b\) 的最大公因数 \(d\) 。
- 对于更为一般的方程 \(ax+by=c\) ,它有整数解当且仅当 \(d|c\) 。
- 令 \(\gcd(a,b)=d,p=\dfrac{b}{d},q=\dfrac{a}{d}\) 。
- 特解:先求出 \(ax+by=d\) 的一组特解 \(x_0,y_0\) ,然后将 \(x_0,y_0\) 各乘上 \(\dfrac{c}{d}\) ,此时就得到了 \(ax+by=c\) 的一组特解 \(x'=\dfrac{c}{d} \times x_0,y'=\dfrac{c}{d} \times y_0\) 。
- \(x\) 的最小正整数解为 \(x_{min}=x'+\left\lceil\dfrac{1-x}{p}\right\rceil \times p\) ,此时 \(y''=y'-\left\lceil\dfrac{1-x}{p}\right\rceil \times q\) 。
- 若 \(y''>0\) ,即存在正整数解时,正整数解的数量为 \(\left\lfloor\dfrac{y''-1}{q}\right\rfloor +1\) ,\(x\) 的最大正整数解为 \(x_{max}=x'+\left\lfloor\dfrac{y''-1}{q}\right\rfloor \times p\) ,\(y\) 的最小正整数解为 \(y_{min}=((y''-1) \bmod q)+1\) ,\(y\) 的最大正整数解为 \(y_{max}=y'\) 。
- 若 \(y'' \le 0\) ,即不存在正整数解时,所有整数解中 \(x\) 的最小正整数值为 \(x_{min}\) , \(y\) 的最小正整数值为 \(y_{min}=y'+\left\lceil\dfrac{1-y}{q}\right\rceil \times q\) 。
- 例题:luogu P5656 【模板】二元一次不定方程 (exgcd)
- \(x\) 的最小正整数解为 \(x_{min}=x'+\left\lceil\dfrac{1-x}{p}\right\rceil \times p\) ,此时 \(y''=y'-\left\lceil\dfrac{1-x}{p}\right\rceil \times q\) 。
- 通解: \(x'=\dfrac{c}{d} \times x_0+pk,y'=\dfrac{c}{d} \times y_0-qk(k \in \mathbb{Z})\) 。其中 \(x_0,y_0,d\) 的定义同上, \(k\) 取遍整数集合。
- 裴蜀定理(贝祖定理, \(Bézout\) 定理)