前置知识

• 一个整数 \(N\) 的约数上界为 \(2\sqrt{N}\) 。
• \(1 \sim N\) 每个数的约数个数的总和大约为 \(N \times logN\) 。
• 取模运算性质
  • \((a+b) \bmod p=((a \bmod p)+(b \mod p)) \mod p\) ，反之亦成立。
  • \((a-b) \bmod p=((a \bmod p)-(b \mod p)) \mod p\) ，反之亦成立。
  • \((a \times b) \bmod p=((a \bmod p) \times (b \mod p)) \mod p\) ，反之亦成立。
  • 引流两篇讲解负数取模的文章 link1 link2
  • 若 \(\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
    • 考虑对更相减损法进行优化：
    • 当 \(a,b\) 均为偶数时，有 \(\gcd(a,b)=2 \times \gcd(\dfrac{a}{2},\dfrac{b}{2})\) 。
    • 当 \(a\) 为偶数， \(b\) 为奇数时，有 \(\gcd(a,b)= \gcd(\dfrac{a}{2},b)\) 。
    • 当 \(b\) 为偶数， \(a\) 为奇数时，有 \(\gcd(a,b)= \gcd(a,\dfrac{b}{2})\) 。
  • 不压位高精TLE 压位高精AC

欧几里得算法

• 若 \(\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;
    }
    

扩展欧几里得算法

• 裴蜀定理（贝祖定理， \(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 【模板】裴蜀定理
  • 代码实现

    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|\) 最小的整数解。
      • 例题：UVA10104 Euclid Problem | CF7C Line
  • 对于更为一般的方程 \(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'=\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\) 取遍整数集合。