Gcd Lcm

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

1. 最大公约数(gcd)

1. 辗转相除法

int gcd(int a, int b) 
    return b ? gcd(b, a % b) : a;
}

2. 更相减损术

• 带取模的

int gcd(int a, int b) {
    int twice = 1;
    while (a % 2 == 0 && b % 2 == 0) {
        a /= 2, b /= 2;
        twice *= 2;
    }
    while(a != b) {
        if(a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return twice * a;
}

• 不带取模的

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

2. 最小公倍数

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