023.最大公约数、同余原理

前置知识：无

求最大公约数 §

欧几里得算法的过程：辗转相除法 §

// 递归
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

// 迭代
func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

正确性证明 §

证明辗转相除法就是证明 $gcd(a,b)=gcd(b,a\%b)$

设 $a\%b=r$，即需要证明的关系为 $gcd(a,b)=gcd(b,r)$

证明：

因为 $a\%b=r$，所以如下两个等式必然成立（$\mathbb{Z}$ 为自然数）

$$\begin{array}{r}a=b\ast q+r,q\in \mathbb{Z}\\ r=a-b\ast q,q\in \mathbb{Z}\end{array}\text{\hspace{1em}(1)(2)}$$

设 $u$ 是 $a$ 和 $b$ 的公因子，则有：$a=s\ast u,b=t\ast u$，其中 $s、t\in \mathbb{Z}$

把 $a$ 和 $b$ 带入 $(2)$ 得到：$r=s\ast u-t\ast u\ast q=(s-t\ast q)\ast u$

这说明：$u$ 如果是 $a$ 和 $b$ 的公因子，那么 $u$ 也是 $r$ 的因子

设 $v$ 是 $b$ 和 $r$ 的公因子，则有：$b=x\ast v,r=y\ast v$，其中 $x、y\in \mathbb{Z}$

把 $b$ 和 $r$ 带入 $(1)$ 得到：$a=x\ast v\ast q+y\ast v=(x\ast q+y)\ast v$

这说明：$v$ 如果是 $b$ 和 $r$ 的公因子，那么 $v$ 也是 $a$ 的公因子

综上：$a$ 和 $b$ 的每一个公因子也是 $b$ 和 $r$ 的一个公因子，反之亦然

所以：$a$ 和 $b$ 的全体公因子集合 $=$ $b$ 和 $r$ 的全体公因子集合，即 $gcd(a,b)=gcd(b,r)$

证毕

复杂度 §

求 gcd(a, b)，其中 a > b，时间复杂度为 $O((loga{)}^3)$

时间复杂度证明略，这个复杂度足够好了

求最小公倍数 §

简单转化就可以求最小公倍数：如果 a 和 b 的最大公约数是 c，则 a 和 b 的最小公倍数为 a/c*b

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

备注 §

更高效求最大公约数的 Stein 算法、由最大公约数扩展出的“裴蜀定理”，比赛同学有兴趣可以继续研究

不比赛的同学，哪怕你的目标是最顶级的公司应聘、还是考研，掌握这个只有一行的函数已经足够！

同余原理 §

背景 §

某些题目计算（加减乘除）过程中的数值会很大，可能导致溢出，一般这种题会要求将答案模一个大质数得到一个非负结果返回（像 这样）

怎么做能够避免计算导致的溢出呢？

1. 使用 bigint 或其他一些大数计算库
2. 同余原理

方法 1 是不太好的，因为数值太大的话，加减乘除的时间复杂度不再是 $O(1)$，k 位（比特位）的大数加减时间复杂度是 $O(k)$，乘除时间复杂度是 $O(k^2)$

同余原理 §

• 加法、乘法：每一步计算完后直接取模
• 减法：(a-b+mod)%mod（避免得到负数结果）
• 要确保过程中不溢出，往往乘法运算的用 long 类型做中间变量
• 除法的同余需要求逆元，会在【扩展】课程里讲述，较难的题目才会涉及

验证 §

package main
 
import (
	"fmt"
	"math"
	"math/big"
	"math/rand"
)
 
const (
	MAX_INT64 = math.MaxInt64
	MOD = 1e9 + 7
	TEST_TIME = 100000
)
 
func main() {
	for i := 0; i < TEST_TIME; i++ {
		a := random()
		b := random()
		c := random()
		d := random()
		r1 := f1(a, b, c, d)
		r2 := f2(a, b, c, d)
		if r1 != r2 {
			panic("error")
		}
	}
	fmt.Println("success")
}
 
// big.Int
// 计算 ((a + b) * (c - d) + (a * c - b * d)) % mod 的非负结果
func f1(a, b, c, d int64) int32 {
	// 将参数转换为 big.Int 类型
	bigA := big.NewInt(a)
	bigB := big.NewInt(b)
	bigC := big.NewInt(c)
	bigD := big.NewInt(d)
	bigMod := big.NewInt(MOD)
	
	// 计算 (a + b) * (c - d)
	tmp1 := new(big.Int).Add(bigA, bigB)
	tmp2 := new(big.Int).Sub(bigC, bigD)
	tmp3 := new(big.Int).Mul(tmp1, tmp2)
	
	// 计算 a * c
	tmp4 := new(big.Int).Mul(bigA, bigC)
	// 计算 b * d
	tmp5 := new(big.Int).Mul(bigB, bigD)
	// 计算 (a * c - b * d)
	tmp6 := new(big.Int).Sub(tmp4, tmp5)
	
	// 计算 ((a + b) * (c - d) + (a * c - b * d))
	tmp7 := new(big.Int).Add(tmp3, tmp6)
	// 计算最终结果并取模
	result := new(big.Int).Mod(tmp7, bigMod)
	// 将结果转换为 int32
	return int32(result.Int64())
}
 
// 同余原理
// 计算 ((a + b) * (c - d) + (a * c - b * d)) % mod 的非负结果
func f2(a, b, c, d int64) int32 {
	aa := a % MOD
	bb := b % MOD
	cc := c % MOD
	dd := d % MOD
	o1 := (aa + bb) % MOD // a + b
	o2 := (cc - dd + MOD) % MOD // c - d
	o3 := (aa * cc) % MOD // a * c
	o4 := (bb * dd) % MOD // b * d
	o5 := (o1 * o2) % MOD // (a + b) * (c - d)
	o6 := (o3 - o4 + MOD) % MOD // (a * c - b * d)
	o7 := (o5 + o6) % MOD // (a + b) * (c - d) + (a * c - b * d)
	return int32(o7)
}
 
func random() int64 {
	return rand.Int63n(MAX_INT64)
}

求最大公约数相关的经典题目 §

题目描述 §

一个正整数如果能被 a 或 b 整除，那么它是神奇的。给定三个整数 n , a , b ，返回第 n 个神奇的数字

因为答案可能很大，所以返回答案 对 $10^9+7$ 取模 后的值

测试链接 §

878.第 N 个神奇数字

思路 §

答案肯定在 $min(a,b)\backsim n\ast min(a,b)$ 之间，假设有一个函数 f(x) 可以返回 $1\backsim x$ 有几个神奇的数字，则可以使用“二分答案法”求解

f(x) 如何实现？

x/a 可以得到 $1\backsim x$ 能被 a 整除的数字个数；x/b 可以得到 $1\backsim x$ 能被 b 整除的数字个数

有数字被重复计数了，就是既能被 a 整除又能被 b 整除的数字，即：x/lcm(a, b) 个，减去即可（“容斥原理”）

答案 §

const (
	mod = 1e9 + 7
)
 
func nthMagicalNumber(n int, a int, b int) int {
	ans := 0
	minn := min(a, b)
	maxx := n * minn
	lcmVal := lcm(a, b)
	for minn <= maxx {
		mid := minn + (maxx-minn)>>1
		if mid/a+mid/b-mid/lcmVal >= n {
			ans = mid
			maxx = mid - 1
		} else {
			minn = mid + 1
		}
	}
	return ans % mod
}
 
func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
 
func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

备注 §

本题用到“二分答案法”和“容斥原理”两个重要的算法，不过用的非常浅，之前没有接触过也能理解

“二分答案法”非常巧妙可以解决很多问题，整套内容会在后续的【必备】课程里做成专题视频讲述

“容斥原理”可以考的非常难，也会在后续的【扩展】课程里做成专题视频讲述