SyntaxPilot
Courses/Competitive Programming/Lesson 19

Competitive Programming · Lesson 19 of 90 · 14 min

Number theory 1: divisibility, GCD/LCM, the Euclidean algorithm

queued

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. d divides a when a ÷ d leaves 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 whole bs as possible: a % b = a − q·b, where q = a / b rounded 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. a is a multiple of d when d divides a. 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 a and 0 are just the divisors of a, and the greatest is a itself. 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 t halls; hall number i is a × 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
3
12 8
7 5
6 6
4
1
6

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.

  1. Cut off the biggest square you can: 8 × 8. A 4 × 8 strip is left (12 − 8 = 4).
  2. Cut the biggest squares off that strip: two of 4 × 4. Nothing is left (8 = 2 · 4).
  3. 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 d divides a and b, then d divides a − q·b = r.
  • If d divides b and r, then d divides q·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, then a % b < b ≤ a / 2.
  • If b > a / 2, then a holds b only once, so a % 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 n benches with lengths a[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
4
12 18 7 24
6
2
4 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 first i numbers, a[0 … i − 1]; pre[0] = 0 (empty).
  • Suffix GCD suf[i] = GCD of a[i − 1 … n − 1], from position i to 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:

  1. g(a, b) iterative and recursive (with the base case), plus a step counter.
  2. lcm(a, b) = a / g * b, with a check that warns when the result would exceed 10^18 (test a / g > 10^18 / b before multiplying).
  3. foldGcd(vector) starting from 0, and prefixGcd / suffixGcd arrays.
  4. A stress test: compare your g against std::gcd and your One Absent against the brute force on random inputs, like episode 16.
  5. Print the Euclid steps for every pair of neighbouring Fibonacci numbers and watch the count grow by one each time.

Practice

  1. (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>).

  2. (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.

  3. (Homework 3) Count pairs i < j with gcd(a[i], a[j]) = 1, n ≤ 2000. Try 1 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.

  4. (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.

  5. What are gcd(0, 7) and gcd(0, 0) with std::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

  1. 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.
  2. 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).
  3. How do you compute the LCM without overflow? a / gcd(a, b) * b: divide first. a * b / gcd overflows even when the answer fits.
  4. What is gcd(a, 0), and why is 0 the starting value of a GCD fold? a; every number divides 0, so gcd(0, x) = x and 0 never changes the result, like 0 for a sum.
  5. 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 trick sum − 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

  • d divides a ⇔ a % d == 0; the GCD is the biggest common divisor, coprime means GCD 1, and gcd(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): a at 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 / g printed 4007528 instead of 2000000000000.
  • One Absent: prefix and suffix GCDs starting at 0, answer max gcd(pre[i − 1], suf[i + 1]), O(n log), 6 instantly on 2·10^5 benches.
  • Real bugs: overflow in a * b / g; no base case → TLE at -O2, SIGFPE at -O0; starting at 1 prints 1.

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.