Math Tricks

目录

• 十进制
  • 从 integer N 取 digits
  • 把 digits 组合成 integer N
• Gosper's Hack
• 因子
  • GCD
  • LCM
  • N能被因子d整除的个数
  • N的因子对的总数
  • N的因子的总数

十进制

从 integer N 取 digits

• n % 10 得到末位
• n / 10 砍掉末位

把 digits 组合成 integer N

n := 0
for each digit {
    n = (n * 10) + digit
}

Gosper's Hack

• 通过位运算，用二进制数模拟生成所有组合数 ${n \choose k}$.
• 注意！只适合 $n$ 比较小的情况。$n \leq 32$.

func GospersHack(n int, k int) {

	state := (1 << k) - 1

	for state < (1 << n) {

		// do something with current combination
		doSomething(state)

		c := state & -state
		r := state + c
		state = (((r ^ state) >> 2) / c) | r
	}
}

• Time complexity = $O({n \choose k})$
• Resources:
  1. Gosper's Hack Explained
     • Explain the mechanism of Gosper's Hack pretty well!!!
  2. 算法学习笔记(75): Gosper's Hack

因子/Divisor

GCD (Greatest Common Divisor)

• Euclidean Algorithm (辗转相除法)

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

LCM (Least Common Multiple)

lcm(a, b) = a * b / gcd(a, b)

N能被因子d整除的个数

• [1, ..., N] 自然数区间内能被 d 整除的个数 = N / d

N的因子对的总数

• 一个整数 n 的因子对 (Divisor Pair)的总数的上限 = sqrt(n)
  • 因为 sqrt(n) 把 n 的所有因数分成左右两边，如果一个因子在sqrt(n)的右边，则必然有一个与之配对的因子在左边。所以，n的因子对的总数最多不超过 [1, ..., sqrt(n)] 的长度，也就是总数上限为sqrt(n)。
    • 注意！sqrt(n)只能是一个上限估计，不完全准确！
  • n的所有因子对中偏小的divisor，一定在[1, ..., sqrt(n)]范围内。
  • e.g. n = 12: divisors = 1, 2, 3, 4, 6, 12; divisor pairs = (1, 12), (2, 6), (3, 4)
    • $\sqrt{12} = 2\sqrt{3} = 2\cdot 1.732 \approx 3.4$. 因子对有3对.
  • e.g. n = 16: divisors = 1, 2, 4, 8, 16; divisor pairs = (1, 16), (2, 8), (4, 4)
    • $\sqrt{16} = 4$. 因子对有3对, 不超过4对.

N的因子的总数

• 如果 n 刚好能开平方, 因子总数 = 2 * 因子对总数 - 1 (因为 sqrt(n)自己跟自己配对)
  • n = 16: divisors = 2 * 3 - 1 = 5
• 如果 n 不能开平方, 因子总数 = 2 * 因子对总数
  • n = 12: divisors = 2 * 3 = 6
• 规律: 如果正整数n有奇数个因子,则n为完全平方数
• 因子个数求解公式: 将整数n分解为质因子乘积形式, 然后将每个质因子的幂分别加一相乘. n=(a*a*a)*(b*b)*(c), 则因子个数=(3+1)(2+1)(1+1)
  • 200=(222) * (5*5). 因子个数=(3+1)(2+1)=12个