基本概念#

发布于2021-01-16

上次编辑2021-04-19

最大公约数

int gcd(int a, int b) {
    int m;
    while (b) m = a % b, a = b, b = m;
    return a;
}

最小公倍数

1	`int lcm(int a, int b) { return a * b / gcd(a, b); }`

和为 \(n\) 的所有数乘积最大

问题：\(n=\sum(a_i)\to\max(\prod(a_i)).\)

结论：将这个数尽量分成 3，如果最后剩下 1，则减去一个 3，分成两个 2.

乘积为 \(n\) 的所有数之和最小

问题：\(n=\prod(a_i)\to\max(\sum(a_i)).\)

结论：\(n\) 的所有素数因子之和。

向上取整

\(a \div b\) 向上取整。

1	`(a + b - 1) // b`

例题#