Alg | 约数 | 忆の風

列出约数

code

朴素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func getDivisors(n int) []int {
	res := make([]int, 0)

	// 约数是成对出现的,添加一个，再添加除的的结果的那个
	for i := 1; i <= n/i; i++ {
		if n%i == 0 {
			res = append(res, i)
			if n/i != i { // 不重复添加
				res = append(res, n/i)
			}
		}
	}

	sort.Ints(res)
	return res
}

约数个数

约数之和

最大公约数

更相减损术

$$ \forall a,b \in \mathbb{N},a \ge b, \qquad gcd(a,b) = gcd(b, a \ - \ b) = gcd(a,a \ - \ b) $$

$$ \forall a,b \in \mathbb{N}, \qquad gcd(2a,2b) = 2gcd(a,b) $$

Proof

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func gcd(a, b int) int {
	for a != b {
		if a > b {
			a -= b
		} else {
			b -= a
		}
	}
	return a
}

欧几里得（辗转相除法）

$$ \forall a,b \in \mathbb{N},b \neq 0, \qquad gcd(a,b) = gcd(b, a \ mod \ b) $$

Proof

Code

1
2
3
4
5
6


func gcd(a, b int) int {
	if b != 0 {
		return gcd(b, a%b)
	}
	return a
}