These are the notes for Competitive Programming episode 19, the start of number theory (the maths of whole numbers). A hall floor has to be covered with the biggest square tiles that fit exactly, and that question needs the greatest common divisor (GCD). We define divisibility from zero, write an original problem, Square Tiles, and watch a brute force that counts down get Time Limit Exceeded on sides of 10^18. Cutting the biggest square off a sheet of paper again and again reveals Euclid's algorithm, gcd(a, b) = gcd(b, a % b), which answers the same hall in 2 steps and never needs more than about 120. Then the LCM with two buses, a second original problem, One Absent, solved with prefix and suffix GCDs in O(n log), and three bugs with real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook: tiling a hall floor
A hall is 12 × 8 metres. The owner wants square tiles, all the same size, and no tile may be cut.
| Tile side | Fits? | Tiles needed |
|---|---|---|
| 1 m | yes | 96 |
| 2 m | yes | 24 |
| 3 m | no: 12 ÷ 3 = 4, but 8 ÷ 3 = 2.67, a row would need a cut tile | — |
| 4 m | yes | 6 |
Bigger tiles mean less work, and the side has to fit into both lengths exactly. The biggest such side is 4. That number has a name: the greatest common divisor.
Divisibility, from zero
- Divides.
ddividesawhena ÷ dleaves no remainder. In C++:a % d == 0. Example: 4 divides 12 (12 = 3 · 4), but 5 does not (12 % 5 = 2). - Remainder / mod.
a % b(read "a mod b") is what is left after taking out as many wholebs as possible:a % b = a − q·b, whereq = a / brounded down. Example:48 % 18 = 12, because 48 = 2 · 18 + 12. - Divisor. A divisor of a number is any number that divides it. Divisors of 12:
1 2 3 4 6 12. Divisors of 8:1 2 4 8. - Multiple.
ais a multiple ofdwhenddividesa. Multiples of 12: 12, 24, 36, 48, … - Common divisor. A number that divides both: for 12 and 8 these are 1, 2 and 4.
- GCD (greatest common divisor). The biggest common divisor:
gcd(12, 8) = 4. It is the side of our tile. - Coprime. Two numbers are coprime when their GCD is 1: they share no divisor except 1. Example:
gcd(7, 5) = 1. - gcd(a, 0) = a. Every number divides 0 (0 ÷ d leaves no remainder), so the common divisors of
aand0are just the divisors ofa, and the greatest isaitself. Example:gcd(7, 0) = 7. You will use this twice today.
The problem: Square Tiles
Problem T · Square Tiles (written for this course). There are
thalls; hall numberiisa × b. Cover each floor exactly with equal square tiles, no cutting. Print the side of the biggest tile that works, one line per hall.
1 ≤ t ≤ 10^5,1 ≤ a, b ≤ 10^18.
| Sample input | Sample output |
|---|---|
312 87 56 6 |
416 |
A side s covers an a × b floor exactly ⇔ s divides a and s divides b, so the answer is gcd(a, b). With 7 × 5 only 1 × 1 tiles fit; with 6 × 6 one tile covers everything. Sides up to 10^18 need long long (an int stops at about 2.1·10^9).
Brute force: count down (Time Limit Exceeded)
Start from the smaller side and count down; the first d that divides both is the answer.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll a, b;
cin >> a >> b;
ll ans = 1;
for (ll d = min(a, b); d >= 1; d--)
if (a % d == 0 && b % d == 0) {
ans = d;
break;
}
cout << ans << "\n";
}
return 0;
}
| Input | Output |
|---|---|
| the sample | 4 1 6 |
1 / 1000000000000000000 999999999999999999 |
Time Limit Exceeded |
Two neighbouring numbers (like 10^18 and 10^18 − 1) share no divisor except 1: any d dividing both would also divide their difference, 1. So the loop counts down about 10^18 times. Even at 10^9 steps a second that is over 30 years.
Euclid's idea: cut the biggest square off, again and again
Take a 12 × 8 sheet of paper and a pair of scissors.
- Cut off the biggest square you can: 8 × 8. A 4 × 8 strip is left (12 − 8 = 4).
- Cut the biggest squares off that strip: two of 4 × 4. Nothing is left (8 = 2 · 4).
- The last square size, 4, is the answer.
Why? A tile that fits the 4 × 8 strip has a side dividing 4 and 8, so it also fits the 8 × 8 square we cut off, so it fits the whole sheet. And a tile that fits the whole sheet and the 8 × 8 square also fits what is left. Cutting never changes which tiles work.
Cutting one square at a time is slow when one side is huge (10^18 × 1 needs 10^18 cuts). But cutting all the q squares of side b in one go leaves a − q·b, which is exactly a % b.
Euclid's rule, and why it is true
gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
Write r = a % b = a − q·b.
- If
ddividesaandb, thenddividesa − q·b = r. - If
ddividesbandr, thenddividesq·b + r = a.
So the pairs (a, b) and (b, r) have exactly the same common divisors, so the same greatest one. Repeat until the second number is 0, then the answer is the first number.
By hand: gcd(48, 18)
| Step | a | b | a % b |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
| end | 6 | 0 | — |
b = 0, so gcd(48, 18) = 6, in 3 steps. (If a < b, the first step just swaps them: 5 % 7 = 5, so (5, 7) → (7, 5).)
The same trace in code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll a = 48, b = 18;
while (b != 0) {
cout << a << " " << b << "\n";
ll r = a % b;
a = b;
b = r;
}
cout << "gcd = " << a << "\n";
return 0;
}
Real output:
48 18
18 12
12 6
gcd = 6
The Euclid solution to Problem T
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll g(ll a, ll b) {
while (b != 0) {
ll r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll a, b;
cin >> a >> b;
cout << g(a, b) << "\n";
}
return 0;
}
| Input | Output | Why |
|---|---|---|
| the sample | 4 1 6 |
as above |
1 / 1000000000000000000 999999999999999999 |
1 (instantly) |
10^18 % (10^18 − 1) = 1, then anything % 1 = 0: 2 steps |
3 / 1 1000000000000000000 / 48 18 / 1000000000000000000 500000000000000000 |
1 6 500000000000000000 |
a side of 1; the trace pair; the smaller side divides the bigger, so it is the answer |
The hall that timed out now takes 2 steps instead of a billion billion.
Why Euclid is O(log): halving and the Fibonacci worst case
Logarithmic time, written O(log n), means the number of steps grows like the number of digits (or bits) of the input, not like the input itself. Doubling the input adds only about one step. 10^18 has about 60 bits, so log-time means "dozens of steps", not "10^18 steps".
The halving argument. Look at one step a → a % b (with a ≥ b):
- If
b ≤ a / 2, thena % b < b ≤ a / 2. - If
b > a / 2, thenaholdsbonly once, soa % b = a − b < a / 2.
Either way, the remainder is less than half of a. The remainder becomes the new b after one step and the new a after two steps, so every two steps, a at least halves. A 60-bit number can be halved only about 60 times, so Euclid needs at most about 120 steps for numbers up to 10^18. That is O(log min(a, b)).
The worst case: Fibonacci numbers. The Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, …, where each number is the sum of the two before it. For two neighbouring Fibonacci numbers, F(k+1) % F(k) = F(k−1): each step takes away just one copy and moves down by only one place, the slowest Euclid can go. Let's count:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int steps(ll a, ll b) {
int s = 0;
while (b != 0) {
ll r = a % b;
a = b;
b = r;
s++;
}
return s;
}
int main() {
cout << steps(1000000000000000000LL, 999999999999999999LL) << " steps\n";
ll f1 = 1, f2 = 1; // Fibonacci numbers
while (f2 <= (ll)1e18 - f1) {
ll f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
cout << f2 << " " << f1 << "\n";
cout << steps(f2, f1) << " steps\n";
return 0;
}
Real output:
2 steps
679891637638612258 420196140727489673
85 steps
The loop condition f2 <= 1e18 - f1 (instead of f1 + f2 <= 1e18) stops before the sum is computed, so it can never overflow. The two largest neighbouring Fibonacci numbers up to 10^18 need just 85 steps: that is the worst Euclid ever gets at this size, comfortably under the halving bound of about 120. A lakh (10^5) of halls is at most about 8.5 million steps: instant.
LCM: two buses from the same depot
Bus A leaves the depot every 12 minutes, bus B every 18. Both left at 9:00. When do they leave together again?
- Bus A: 12, 24, 36, 48, … (the multiples of 12)
- Bus B: 18, 36, 54, … (the multiples of 18)
At 36 minutes, 9:36. The smallest number that is a multiple of both is the least common multiple, LCM: lcm(12, 18) = 36.
You don't need to list times. a · b = gcd(a, b) · lcm(a, b), so
lcm(a, b) = a / gcd(a, b) * b. Example: 12 / 6 · 18 = 2 · 18 = 36.
Why the formula holds: write g = gcd(a, b), a = g·x, b = g·y. Then x and y are coprime (any common divisor bigger than 1 would make the GCD bigger than g). A common multiple must contain g·x and g·y; since x and y share nothing, the smallest one is g·x·y. And g · (g·x·y) = (g·x)·(g·y) = a·b.
Divide first. a / g is always a whole number (g divides a), and dividing first keeps the numbers small. a * b / g computes a · b first, which can be far bigger than long long (about 9.2·10^18) even when the LCM itself fits. That is overflow: a value too big for its type wraps around to garbage (for signed integers it is undefined behaviour).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll g(ll a, ll b) {
while (b != 0) {
ll r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
ll a = 12, b = 18;
cout << "gcd " << g(a, b) << ", lcm " << a / g(a, b) * b << "\n";
ll c = 1000000000000LL, d = 2000000000000LL;
cout << "lcm " << c / g(c, d) * d << "\n";
cout << "std " << gcd(c, d) << " " << lcm(c, d) << "\n";
return 0;
}
Real output:
gcd 6, lcm 36
lcm 2000000000000
std 1000000000000 2000000000000
36 for the buses, two trillion for the big pair. std::gcd and std::lcm (C++17, header <numeric>, included by <bits/stdc++.h>) agree. Both arguments must have the same type, so gcd(c, 5) with c a long long needs 5LL.
Part 2: Problem One Absent
Problem T2 · One Absent (written for this course). A carpenter has
nbenches with lengthsa[0], …, a[n − 1]. He throws away exactly one bench, then cuts every other bench into equal pieces with no waste, as long as possible. Print the longest possible piece length.
2 ≤ n ≤ 2·10^5,1 ≤ a[i] ≤ 10^18.
| Sample input | Sample output |
|---|---|
412 18 7 24 |
6 |
24 9 |
9 |
A piece length works for the remaining benches ⇔ it divides all of them, so the answer is the maximum over every i of the GCD of all numbers except a[i]. In the sample, throwing away the 7 leaves gcd(12, 18, 24) = 6. With two benches you keep the longer one and the piece is the whole bench: 9.
The GCD of many numbers is a fold: gcd(a, b, c) = gcd(gcd(a, b), c), and so on, left to right. Start from 0, because gcd(0, x) = x: 0 is the neutral (identity) value of GCD, a starting value that changes nothing, just as a sum starts at 0 and a product at 1. Example: gcd(0, 12) = 12, gcd(12, 18) = 6, gcd(6, 24) = 6.
Brute force: skip each bench (Time Limit Exceeded)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (auto &x : a) cin >> x;
ll best = 0;
for (int skip = 0; skip < n; skip++) {
ll cur = 0;
for (int i = 0; i < n; i++)
if (i != skip) cur = gcd(cur, a[i]);
best = max(best, cur);
}
cout << best << "\n";
return 0;
}
The worst case is built inside main (same loop body):
int main() {
int n = 200000; // worst case, built here
vector<ll> a(n);
for (int i = 0; i < n; i++) a[i] = 6LL * (i + 1);
ll best = 0;
for (int skip = 0; skip < n; skip++) {
ll cur = 0;
for (int i = 0; i < n; i++)
if (i != skip) cur = gcd(cur, a[i]);
best = max(best, cur);
}
cout << best << "\n";
return 0;
}
| Input | Output |
|---|---|
4 / 12 18 7 24 |
6 |
2 / 4 9 |
9 |
n = 200000, a[i] = 6·(i + 1) (built in main) |
Time Limit Exceeded (n skips × n numbers = 4·10^10 GCDs) |
The fix: prefix and suffix GCD
The idea comes from episode 7, prefix sums. All numbers except a[i] are exactly a left part and a right part:
[ a[0] … a[i−1] ] a[i] [ a[i+1] … a[n−1] ]
pre: left skip suf: right
With 1-based positions (a[i − 1] is the i-th bench):
- Prefix GCD
pre[i]= GCD of the firstinumbers,a[0 … i − 1];pre[0] = 0(empty). - Suffix GCD
suf[i]= GCD ofa[i − 1 … n − 1], from positionito the right end;suf[n + 1] = 0(empty). - GCD without bench
i=gcd(pre[i − 1], suf[i + 1]).
For the sample 12 18 7 24:
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| bench | 12 | 18 | 7 | 24 |
pre[i] |
12 | 6 | 1 | 1 |
suf[i] |
1 | 1 | 1 | 24 |
without bench i: gcd(pre[i−1], suf[i+1]) |
gcd(0, 1) = 1 | gcd(12, 1) = 1 | gcd(6, 24) = 6 | gcd(1, 0) = 1 |
An empty part must change nothing, so pre and suf start at 0, not 1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (auto &x : a) cin >> x;
vector<ll> pre(n + 1, 0), suf(n + 2, 0);
for (int i = 1; i <= n; i++) pre[i] = gcd(pre[i - 1], a[i - 1]);
for (int i = n; i >= 1; i--) suf[i] = gcd(suf[i + 1], a[i - 1]);
ll best = 0;
for (int i = 1; i <= n; i++)
best = max(best, gcd(pre[i - 1], suf[i + 1]));
cout << best << "\n";
return 0;
}
| Input | Output | Why |
|---|---|---|
4 / 12 18 7 24 |
6 |
drop the 7 |
2 / 4 9 |
9 |
keep the longer bench |
n = 200000, a[i] = 6·(i + 1) (same pre/suf code, array built in main) |
6 (instantly) |
every bench is a multiple of 6 |
Three passes of n GCDs each: O(n log). A stress test against the brute force on 300 random arrays (n ≤ 8, values ≤ 60) found no difference.
Complexity
| Method | Time | Worst case here | Verdict |
|---|---|---|---|
| T: count down from min(a, b) | O(min(a, b)) per hall | up to 10^18 steps | TLE |
| T: Euclid | O(log min(a, b)) per hall | ≤ 85 steps (Fibonacci), bound ≈ 120 | instant |
| T2: skip each, fold the rest | O(n² log) | 4·10^10 GCDs | TLE |
| T2: prefix + suffix GCD | O(n log) | 3 · 2·10^5 GCDs | instant |
LCM via a / g * b |
O(log) | one GCD | instant |
Memory: O(1) for T, O(n) for T2 (two extra arrays).
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
lcm = c * d / g(c, d) with c = 10^12, d = 2·10^12 |
lcm 4007528 instead of lcm 2000000000000 |
c * d = 2·10^24 overflows long long before the division can help |
divide first: c / g(c, d) * d |
Recursive GCD with no base case: return g(b, a % b); |
Time Limit Exceeded on the 3-hall sample at -O2; Floating point exception (SIGFPE) at -O0 |
when b reaches 0 it still computes a % 0, which is undefined behaviour |
if (b == 0) return a; first |
pre(n + 1, 1), suf(n + 2, 1) |
1 instead of 6 on 12 18 7 24 |
gcd(1, x) = 1 swallows every answer |
start at 0: gcd(0, x) = x |
Counting down from min(a, b) |
Time Limit Exceeded on 10^18 and 10^18 − 1 |
10^18 steps | Euclid, or std::gcd |
The recursive bug, exactly as shown in the video:
ll g(ll a, ll b) {
return g(b, a % b);
}
Undefined behaviour means the C++ standard says nothing about what the program does: the compiler may assume it never happens. Dividing by zero is undefined. With -O2 the compiler assumed a % 0 never happens, so the recursion with no exit turned into an endless loop: the judge reports Time Limit Exceeded. Compiled with -O0 (no optimisation), the same code really divides by zero and the processor stops it with a floating point exception (SIGFPE), even though no floating-point number is involved. Either way the fix is the same:
ll g(ll a, ll b) {
if (b == 0) return a;
return g(b, a % b);
}
Mini project
Build a GCD toolbox in one file:
g(a, b)iterative and recursive (with the base case), plus a step counter.lcm(a, b) = a / g * b, with a check that warns when the result would exceed 10^18 (testa / g > 10^18 / bbefore multiplying).foldGcd(vector)starting from 0, andprefixGcd/suffixGcdarrays.- A stress test: compare your
gagainststd::gcdand your One Absent against the brute force on random inputs, like episode 16. - Print the Euclid steps for every pair of neighbouring Fibonacci numbers and watch the count grow by one each time.
Practice
-
(Homework 1) Print the GCD of the whole array, and the GCD of every prefix, for
12 18 24 7.Answer
Fold from 0: <code>gcd(0, 12) = 12</code>, <code>gcd(12, 18) = 6</code>, <code>gcd(6, 24) = 6</code>, <code>gcd(6, 7) = 1</code>. Prefix GCDs: <code>12 6 6 1</code>; whole array: 1. Prefix GCDs can only stay the same or drop to a divisor, so they change at most about log(a[0]) times. Checked by running the fold in C++ (output <code>12 6 6 1</code>). -
(Homework 2) You may change one element to any positive number you like. Maximise the GCD of the whole array (n ≥ 2).
Answer
It is exactly One Absent. The changed element can be set to the GCD of the others (or a multiple of it), so the GCD equals the GCD of the others; and the GCD can never exceed the GCD of the others, because it must divide them. So the answer is <code>max over i of gcd(pre[i − 1], suf[i + 1])</code>, O(n log). For <code>12 18 7 24</code> it is 6: a brute force over every position and every replacement value 1…200 also printed 6. -
(Homework 3) Count pairs
i < jwithgcd(a[i], a[j]) = 1, n ≤ 2000. Try1 2 3 4 6.Answer
Two loops over all pairs: n(n − 1)/2 ≈ 2·10^6 GCDs, each O(log): fast enough. For <code>1 2 3 4 6</code> the coprime pairs are (1,2), (1,3), (1,4), (1,6), (2,3), (3,4): <b>6</b> (the program printed <code>coprime pairs 6</code>). Note 1 is coprime with everything. -
(Homework 4) Prove
lcm(a, b) · gcd(a, b) = a · b.Answer
Let <code>g = gcd(a, b)</code>, <code>a = g·x</code>, <code>b = g·y</code>, with <code>x</code>, <code>y</code> coprime (a common divisor d > 1 of x and y would make g·d a bigger common divisor). <code>g·x·y</code> is a multiple of both. Any common multiple m is a multiple of g·x; write m = g·x·k; then g·y divides g·x·k, so y divides x·k, and since y shares nothing with x, y divides k. So m ≥ g·x·y, and lcm = g·x·y. Then lcm · g = (g·x)(g·y) = a·b. Also checked by program for every pair 1 ≤ a, b ≤ 300. -
What are
gcd(0, 7)andgcd(0, 0)withstd::gcd, and why does the first matter for prefix GCDs?Answer
<code>gcd(0, 7) = 7</code> (every number divides 0), and <code>std::gcd(0, 0)</code> returns <code>0</code> (real output <code>0 7</code>). Because <code>gcd(0, x) = x</code>, 0 is the neutral start: an empty prefix or suffix changes nothing.
Quick quiz
gcd(84, 36) and lcm(84, 36)?
A) 6 and 504 · B) 12 and 252 · C) 12 and 3024 · D) 4 and 756
Answer
B. 84 % 36 = 12, then 36 % 12 = 0, so the GCD is 12. LCM = 84 / 12 · 36 = 7 · 36 = 252. std::gcd and std::lcm print 12 252. (C is 84 · 36 / 1: forgetting to divide by the GCD.)
Interview questions
- State Euclid's algorithm and prove it.
gcd(a, b) = gcd(b, a mod b),gcd(a, 0) = a. Any d dividing a and b divides a − q·b, and any d dividing b and a − q·b divides a, so both pairs have the same common divisors. - What is its time complexity, and what is the worst input? O(log min(a, b)): the first number at least halves every two steps. The worst case is two neighbouring Fibonacci numbers (85 steps below 10^18).
- How do you compute the LCM without overflow?
a / gcd(a, b) * b: divide first.a * b / gcdoverflows even when the answer fits. - What is gcd(a, 0), and why is 0 the starting value of a GCD fold?
a; every number divides 0, sogcd(0, x) = xand 0 never changes the result, like 0 for a sum. - How do you answer "the GCD of everything except one element" for every element? Prefix and suffix GCD arrays; answer
gcd(pre[i − 1], suf[i + 1])in O(1) each after O(n log) building. GCD has no inverse (you can't "subtract" a number out of a GCD), so the prefix-sum tricksum − a[i]does not work: you need both sides.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Number theory | The maths of whole numbers: divisibility, primes, remainders | this episode and the next |
| Divides | d divides a when a % d == 0 |
4 divides 12 |
Remainder / mod (%) |
What is left after taking out whole copies: a − q·b |
48 % 18 = 12 |
| Divisor | A number that divides another | divisors of 8: 1 2 4 8 |
| Multiple | a is a multiple of d when d divides a |
36 is a multiple of 12 and 18 |
| GCD | Greatest common divisor | gcd(12, 8) = 4 |
| Coprime | GCD equals 1 | 7 and 5 |
| LCM | Least common multiple | lcm(12, 18) = 36 |
| Euclidean algorithm | Replace (a, b) with (b, a % b) until b = 0 |
48 18 → 18 12 → 12 6 → 6 0 |
| Fibonacci numbers | Each is the sum of the two before | 1 1 2 3 5 8 13 |
| Logarithmic time, O(log n) | Steps grow like the number of digits | ≤ ~120 steps at 10^18 |
| Fold | Combine a list one element at a time | gcd(gcd(12, 18), 24) |
| Prefix / suffix GCD | GCD of everything left of / right of a position | pre = 12 6 1 1 |
| Neutral (identity) value | A start that changes nothing | 0 for GCD and sum, 1 for product |
| Overflow | A value too big for its type wraps to garbage | c * d = 2·10^24 |
| Undefined behaviour | Code the C++ standard gives no meaning to; anything may happen | a % 0 |
| SIGFPE | The signal for an arithmetic error such as integer division by zero | "Floating point exception" |
std::gcd, std::lcm |
C++17 functions in <numeric> |
gcd(12LL, 18LL) = 6 |
Summary
ddividesa⇔a % d == 0; the GCD is the biggest common divisor, coprime means GCD 1, andgcd(a, 0) = a.- Counting down from
min(a, b)is correct but got TLE on 10^18 and 10^18 − 1. - Cutting squares off a sheet gives Euclid:
gcd(a, b) = gcd(b, a % b), proved with common divisors. - O(log):
aat least halves every two steps; the Fibonacci worst case below 10^18 needs only 85 steps; the big hall needs 2. lcm = a / g * b;a * b / gprinted4007528instead of2000000000000.- One Absent: prefix and suffix GCDs starting at 0, answer
max gcd(pre[i − 1], suf[i + 1]), O(n log),6instantly on 2·10^5 benches. - Real bugs: overflow in
a * b / g; no base case → TLE at-O2, SIGFPE at-O0; starting at 1 prints1.
Solutions in C++, Java and Python
C++: Problem T is the Euclid program above (or replace g(a, b) with gcd(a, b)); Problem T2 is the prefix/suffix program above.
Problem T · Square Tiles
Java (tested: sample → 4 1 6; 10^18 10^18−1 → 1; edge input → 1 6 500000000000000000):
import java.io.*;
import java.util.*;
public class Main {
static long gcd(long a, long b) {
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return a;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
StringBuilder out = new StringBuilder();
while (t-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
out.append(gcd(a, b)).append('\n');
}
System.out.print(out);
}
}
Python (same tests, same outputs; Python integers never overflow):
import sys
from math import gcd
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(t):
a = int(data[1 + 2 * i])
b = int(data[2 + 2 * i])
out.append(str(gcd(a, b)))
print("\n".join(out))
main()
Problem T2 · One Absent
Java (tested: 12 18 7 24 → 6; 4 9 → 9; 200000 benches 6, 12, … → 6 in about half a second):
import java.io.*;
import java.util.*;
public class Main {
static long gcd(long a, long b) {
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return a;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
long[] a = new long[n];
StringTokenizer st = new StringTokenizer("");
for (int i = 0; i < n; i++) {
while (!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
a[i] = Long.parseLong(st.nextToken());
}
long[] pre = new long[n + 1]; // all 0: gcd(0, x) = x
long[] suf = new long[n + 2];
for (int i = 1; i <= n; i++) pre[i] = gcd(pre[i - 1], a[i - 1]);
for (int i = n; i >= 1; i--) suf[i] = gcd(suf[i + 1], a[i - 1]);
long best = 0;
for (int i = 1; i <= n; i++)
best = Math.max(best, gcd(pre[i - 1], suf[i + 1]));
System.out.println(best);
}
}
Python (same tests, same outputs, and it agreed with the C++ brute force on 300 random arrays):
import sys
from math import gcd
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
pre = [0] * (n + 1) # gcd(0, x) = x, so 0 is the neutral start
suf = [0] * (n + 2)
for i in range(1, n + 1):
pre[i] = gcd(pre[i - 1], a[i - 1])
for i in range(n, 0, -1):
suf[i] = gcd(suf[i + 1], a[i - 1])
best = 0
for i in range(1, n + 1):
best = max(best, gcd(pre[i - 1], suf[i + 1]))
print(best)
main()
Next episode: Number theory 2: sieve, smallest prime factor, factorisation.