YeziSnip

记录、沉淀、分享代码片段。

整数上取整公式

竞赛中，应对整数向上取整的简单方法

// ceil((double)n / a); 限制较多

(n + a - 1) / a;

常常和最大公约数配合使用

int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 先除后乘，防止溢出
}

使用循环实现欧几里得/辗转相除法求最大公约数

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

使用递归实现欧几里得/辗转相除法求最大公约数

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