【学习笔记】简单数论-最大公约数

• 证明：设 \(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\) 同理。

• 考虑对更相减损法进行优化：
  • 当 \(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

• 证明
  • 若 \(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)\) 。

int gcd(int a, int b)
{
	return b?gcd(b,a%b):a;
}

• 对于任意整数 \(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

• 令 \(\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\) 取遍整数集合。