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 \bmod b)$$$% b)`, and when $$$`b = 0$$$` the answer is $$$a$$$`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)↵
↵
$$$\text{`lcm}(a, b) = \frac{a}{\gcd(a, b)} \cdot 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.With $$$a, b \leIf 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) \cdot \text{* lcm}(a, b) = a \cdot b$$$* 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$$$`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 \cdot x$$$, $$$b = g \cdot y$$$* 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 $$$O(\`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, y$$$`x` and `y` such that $$$a \cdot`a * x + b \cdot* 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 \cdot`a * x + b \cdot* y = c$$$` has an integer solution if and only if $$$\`gcd(a, b)$$$` divides $$$c$$$`c`.↵
-* Modular inverse of $$$a$$$`a` modulo $$$m$$$`m` when $$$\`gcd(a, m) = 1$$$`: run `exgcd(a, m, x, y)` and take $$$x$$$`x` modulo $$$m$$$`m` (make it positive!). This works even when $$$m$$$`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:↵
-↵
* [problem:1325A] EhAb AnD gCd↵
-* [problem:1498A] 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.
↵
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:
↵
~~~~~↵
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
↵
One small thing:
↵
### 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.
↵
~~~~~↵
long long lcm(long long a, long long b) {↵
return a / gcd(a, b) * b;↵
}↵
~~~~~↵
↵
Also remember
↵
### 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 + k, b + k)
↵
### 5. Extended Euclid↵
↵
It finds
↵
~~~~~↵
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
↵
### 6. Mistakes I (and probably you) make↵
↵
↵
### 7. Problems to practice↵
↵
Easy ones to start with:↵
* [problem:1325A]
↵
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.
