SOTSOG学习笔记记录
Posts Notes Algorithms Awesome Tags Categories
SOTSOG学习笔记记录

基本概念

基本问题

最大公约数 
1
2
3
4
5

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$ 的所有数乘积最大

  • 5716. 好因子的最大数目

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

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

乘积为 $n$ 的所有数之和最小
向上取整

$a \div b$ 向上取整。

1

(a + b - 1) // b
下一个排列 
1
2
3
4
5
6
7
8
9

def next_permutation(s: List[str]) -> bool:
    n = len(s)
    for i in reversed(range(0, n - 1)):
        if s[i] < s[i + 1]:
            j = next(j for j in reversed(range(i + 1, n)) if s[j] > s[i])
            s[i], s[j] = s[j], s[i]
            s[i + 1 :] = reversed(s[i + 1 :])
            return True
    return False

例题