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:

$, and when

$ the answer is

$.

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

$. Reason: every two steps the bigger number becomes at least half of what it was. So even for

$ it's like 90 steps, nothing to worry about.

One small thing:

$. 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)

$

Please divide first, then multiply. If you do a * b / gcd(a, b), the product can overflow even when the final answer would fit. With

$ the lcm can be up to

$, 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

$. 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

$, so

$ always divides

$. -

$ divides

$ for any

$. This helps in problems where you add the same number to two values and want them to share a factor. - If

$, you can write

$,

$ with

$. A lot of problems become much easier after this substitution. - While you go through an array, the prefix gcd changes at most

$ times, since every time it changes it becomes at most half of the previous value.

5. Extended Euclid

It finds

$ such that

$.

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

$ has an integer solution if and only if

$ divides

$. - Modular inverse of

$ modulo

$ when

$: run exgcd(a, m, x, y) and take

$ modulo

$ (make it positive!). This works even when

$ 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

$, 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: - 1325A - EhAb AnD gCd EhAb AnD gCd - 1498A - GCD Sum GCD Sum

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.