GCD and LCM: the small things I wish I knew earlier

Hi everyone!

I'm not a high-rated guy (just ~1300), so this isn't some deep post. I just noticed that gcd and lcm show up in a LOT of problems, and every time I would forget some tiny detail and lose time on it. So I wrote everything in one place. Maybe it helps someone who is at the same stage as me, and if I got something wrong please tell me in the comments, I'll fix it :)

1. Euclid's algorithm

The whole idea is one line: gcd(a, b) = gcd(b, a % b), and when b = 0 the answer is a.

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

If you use C++17 you can just write std::gcd(a, b) (it's in <numeric>). On older compilers __gcd(a, b) works too.

It runs in O(log(min(a, b))). Reason: every two steps the bigger number becomes at least half of what it was. So even for numbers around 10^18 it's like 90 steps, nothing to worry about.

One small thing: gcd(0, x) = x. This is useful because you can start the gcd of an array from 0 and not worry about the first element.

2. LCM (and the overflow trap)

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

Please divide first, then multiply. If you do a * b / gcd(a, b), the product can overflow even when the final answer would fit. If a and b are up to 10^9, the lcm can be up to 10^18, which fits in long long but definitely not in int.

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

Also remember gcd(a, b) * lcm(a, b) = a * b. It's handy more often than you'd think.

3. GCD of an array

long long g = 0;
for (long long x : a) g = gcd(g, x);

A trick that appears a lot: "what is the gcd if I remove one element?" For this, build prefix and suffix gcd arrays:

// pre[i] = gcd(a[0..i]),  suf[i] = gcd(a[i..n-1])
// gcd without a[i] = gcd(pre[i-1], suf[i+1])

(be careful with the borders, i = 0 and i = n-1. This is where I usually get WA.)

4. Some properties worth remembering

gcd(a, b) = gcd(a, b - a), so gcd(a, b) always divides |a - b|.
gcd(a + k, b + k) also divides |a - b| for any k. This helps in problems where you add the same number to two values and want them to share a factor.
If g = gcd(a, b), you can write a = g * x and b = g * y with gcd(x, y) = 1. A lot of problems become much easier after this substitution.
While you go through an array, the prefix gcd changes at most log(M) times (M is the max value), since every time it changes it becomes at most half of the previous value.

5. Extended Euclid

It finds x and y such that a * x + b * y = gcd(a, b).

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

Where it's useful:

The equation a * x + b * y = c has an integer solution if and only if gcd(a, b) divides c.
Modular inverse of a modulo m when gcd(a, m) = 1: run exgcd(a, m, x, y) and take x modulo m (make it positive!). This works even when m is not prime, unlike Fermat's trick.

6. Mistakes I (and probably you) make

Using int for lcm and getting overflow.
Multiplying before dividing.
Forgetting that gcd(0, 0) = 0, and then dividing by it.
Forgetting that the lcm of a whole array grows really fast, so it may not fit in long long after a few elements.

7. Problems to practice

Easy ones to start with:

After that, go to the problemset, filter by the tag "number theory" and rating 800 to 1500, and solve a few. I'm still doing this myself.

That's all, thanks for reading!

Question for you: what is the most interesting or surprising problem you have seen that uses gcd? I would like to add it to the list. Also if you know a nicer way to explain any part here, please share.