数论知识.md

数论 (TODO)

1. 质数

1.1 判断 整数x 是否为质数

func isPrime(x int) bool {
	if x <= 1 {
		return false
	}
	for i := 2; i*i <= x; i++ {
		if x%i == 0 {
			return false
		}
	}
	return true
}

1.2 获取 [1, n] 中的质数 (素数筛)

func primeGenerator(n int) []int {
	isNotPrime := make([]bool, n+1)
	ans := []int{}

	for i := 2; i*i <= n; i++ {
		if isNotPrime[i] == true {
			continue
		}
		for t := i * i; t <= n; t += i {
			isNotPrime[t] = true
		}
	}
	for i := 2; i <= n; i++ {
		if isNotPrime[i] == false {
			ans = append(ans, i)
		}
	}
	return ans
}

2. 因子

2.1 求一组整数的最大公约数

// 求一组整数的最大公约数
func GCD(nums ...int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	x, y := nums[0], GCD(nums[1:]...)
	if y == 0 {
		return x
	}
	if x == 0 {
		return y
	}
	return GCD(y, x%y)
}

2.2 求一组整数的最小公倍数

// 求一组整数的最小公倍数
func LCM(nums ...int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	x := LCM(nums[1:]...)
	gcd := GCD(x, nums[0])
	return x / gcd * nums[0]
}

// 求一组整数的最大公约数
func GCD(nums ...int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	x, y := nums[0], GCD(nums[1:]...)
	if y == 0 {
		return x
	}
	if x == 0 {
		return y
	}
	return GCD(y, x%y)
}

2.3 求 整数x 的因子和

func getFactorSum(x int) int {
	sum := 0
	for i := 1; i*i <= x; i++ {
		if x%i == 0 {
			sum += i
			if x/i != i {
				sum += x / i
			}
		}
	}
	return sum
}

2.4 求 n! 尾部 0 的个数

func trailingZeroes(n int) int {
	ans := 0
	for n != 0 {
		ans += n / 5
		n = n / 5
	}
	return ans
}

2.5 判断 整数x 是否只有某些因子

// 判断 x 是否只有 factorSet 中的因子
func isOnlyHaving(factorSet []int, x int) bool {
	for i := 0; i < len(factorSet); i++ {
		for x%factorSet[i] == 0 {
			x /= factorSet[i]
		}
	}
	return x == 1
}

3. 定理

3.1 裴蜀定理

$设a_{1},a_{2},a_{3}......a_{n}为n个整数，d是它们的最大公约数，那么存在整数x_{1}......x_{n}使得x_{1}*a_{1}+x_{2}*a_{2}+...x_{n}*a_{n}=d。$
描述出处

1250. 检查「好数组」

3.2 费马小定理

$如果p是一个质数，而整数a不是p的倍数，则有 a^{(p-1)}≡1（mod p）$。
描述出处

3.3 容斥定理

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分.........依此类推，一直计算到所有集合相交的部分。
描述出处

4. 练习题

• 172. 阶乘后的零
• 204. 计数质数
• 263. 丑数
• 507. 完美数
• 1201. 丑数 III
• 1250. 检查「好数组」