15. GCD and LCM — Homework Solutions

The answer .cpp files are in exercises/15/homework/solutions/.

Open this page after trying on your own. Compare your line of thinking with the How to think about it section, not the code line by line: two pieces of code with different shapes can both be correct, and what is worth copying is how to get there. The Tests part of each problem contains input and output that have already been checked — run your own answer with that input before considering yourself done.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/15/homework/solutions/01-fpb-kpk.cpp
./jawab

Problem 1 — GCD and LCM

Problem. Print the GCD and then the LCM of two numbers up to 10¹⁸.

How to think about it. The GCD with the Euclidean algorithm, the LCM from the property GCD × LCM = a × b. What is being tested here is the order of operations: a / g * b, not a * b / g.

Walkthrough.

long long g = fpb(a, b);
cout << g << "\n";
cout << a / g * b << "\n";

Tests.

The second row tests two equal numbers: both the GCD and the LCM are the number itself. The third row tests the order of operations — with a * b / fpb(a, b), the multiplication overflows long before it can be divided.

Common mistakes.

• Writing a * b / g. For a and b of size 4 × 10⁹, the product is already 1.6 × 10¹⁹ and overflows before the division.
• Using prime factorization. For 10¹⁸, the factoring alone takes too long; Euclid finishes in tens of steps.

Problem 2 — Simplify a fraction

Problem. Print p/q in lowest terms.

How to think about it. Divide both by their GCD. A single division already produces the lowest terms — no need to repeat it, because after dividing by the GCD, the numerator and denominator are guaranteed to be coprime.

Walkthrough.

long long g = fpb(p, q);
cout << p / g << "/" << q / g << "\n";

Tests.

The third row is a formatting decision to watch: the problem asks for the form p/q, so 10/1 is correct — not 10. If a real problem asked for the opposite, it would have to say so in the description.

Common mistakes.

• Dividing repeatedly by 2, 3, 5, … until it is no longer possible. Correct, but much longer and error-prone.
• Forgetting that fpb(p, q) is never zero as long as one of them is positive.

Problem 3 — GCD of a sequence of numbers

Problem. The GCD of n numbers.

How to think about it. The GCD can be computed in sequence: GCD(a, b, c) = GCD(GCD(a, b), c). The cleanest initial value is 0, because GCD(0, x) = x — so the first element does not need special treatment.

The data can be processed directly while it is read; no array is needed.

Walkthrough.

long long g = 0;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    g = fpb(g, x);
}
cout << g << "\n";

Tests.

The third row is the reason for the hint in the problem: once the running GCD reaches 1, the rest of the data no longer needs to be checked. For n = 200,000 that cutoff often saves almost the entire loop.

Common mistakes.

• Starting with g = 1. The result is always 1.
• Storing all the data in an array when it is not needed — not a wrong answer, but a waste of memory.

Problem 4 — Blinking lamps

Problem. The next second at which all lamps blink together.

How to think about it. The answer is the LCM of all the intervals, computed in sequence. The initial value 1 is right here, because LCM(1, x) = x.

Watch out for overflow: the running LCM grows quickly. This problem restricts n ≤ 15 and values ≤ 1,000 precisely so that the answer still fits.

Walkthrough.

long long k = 1;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    k = kpk(k, x);
}
cout << k << "\n";

Check 12 18 8: LCM(1, 12) = 12, LCM(12, 18) = 36, LCM(36, 8) = 72.

Tests.

The second row is the most typical mistake on this problem: simply multiplying gives 24, even though the two already meet at second 12.

Common mistakes.

• Starting with k = 0. LCM(0, x) is meaningless, and dividing by the GCD keeps producing zero.
• Using int for k.

Challenge — Modular inverse without Fermat

Problem. The inverse of a modulo m for arbitrary m.

How to think about it. Fermat's little theorem only applies to a prime modulus. For arbitrary m, use extended Euclid: it gives x and y with

a·x + m·y = GCD(a, m)

If the GCD is 1, then modulo m the whole term m·y vanishes, so a·x ≡ 1 (mod m) — meaning x is the inverse. If the GCD is not 1, the inverse simply does not exist.

The returned x can be negative, so normalize it with ((x % m) + m) % m — exactly as in problem 1 of Chapter 14.

Walkthrough.

long long g = fpb_luas(a, m, x, y);

if (g != 1) {
    cout << "TIDAK ADA\n";
    return 0;
}

long long inv = ((x % m) + m) % m;
cout << inv << "\n";
cout << a % m * inv % m << "\n";

Check 3 10: the inverse is 7, and 3 × 7 = 21 ≡ 1 (mod 10). For 4 10 the answer is TIDAK ADA ("does not exist"), because GCD(4, 10) = 2.

Tests.

The second row is the reason this problem exists: 12 is not a prime number, so Fermat's little theorem does not apply and pangkat_mod(a, m - 2, m) would give a wrong answer. Extended Euclid still works as long as GCD(a, m) = 1.

Common mistakes.

• Using pangkat_mod(a, m - 2, m) for a non-prime m. The result is a number that looks reasonable but is wrong — and there is no error message at all. Always check by multiplying back.
• Forgetting to normalize a negative x.

OSN-style exercises — walkthrough

The answer files are in exercises/15/osn/solutions/.

Problem 1 — Largest Square Tile

How to think about it. Translate the conditions one by one. "Nothing left over along the length" means the tile side divides P exactly; "nothing left over along the width" means it also divides L exactly. So what is being sought is the greatest common divisor — the word "largest" in the problem points straight to the GCD.

The number of tiles is the product of the tile counts in both directions: (P / side) × (L / side).

Walkthrough.

long long sisi = fpb(p, l);
long long banyak = (p / sisi) * (l / sisi);

cout << sisi << " " << banyak << "\n";

The upper bound on the number of tiles is P × L = 10¹⁸, which happens when the GCD is 1. That fits in long long but not in int.

Tests.

Common mistakes.

• Using the smallest number as the tile side. For 12 18 that gives 12, which does not divide 18 exactly.
• Finding the GCD by trying every divisor from 1 to P. For P = 10⁹ that is 10⁹ iterations per case.
• Computing the number of tiles as p * l / (sisi * sisi). The result is the same, but p * l overflows first for large values.

Problem 2 — Common Multiples

How to think about it. A number is divisible by both X and Y exactly when it is divisible by LCM(X, Y). So the problem becomes: how many multiples of L lie between A and B?

The number of multiples of L from 1 to n is ⌊n / L⌋. For the range [A, B], the answer is ⌊B / L⌋ − ⌊(A − 1) / L⌋. The A − 1 form is what makes the left endpoint count too.

Walkthrough.

long long kpk = x / fpb(x, y) * y;      // divide first, then multiply
long long banyak = b / kpk - (a - 1) / kpk;

The order x / fpb * y matters. With x * y / fpb, the multiplication 10⁹ × 10⁹ = 10¹⁸ is done first — for these constraints it still fits, but that habit will overflow as soon as the constraints are raised a little.

Tests.

Common mistakes.

• Checking every number from A to B with a loop.
• Using b / kpk - a / kpk, which misses A itself if A happens to be a multiple of the LCM.
• Multiplying X by Y as the LCM without dividing by the GCD. For 5 9 3 3 that approach answers 1, not 2.

Problem 3 — Common Divisor of Differences

How to think about it. The phrase "same remainder" looks hard because the remainder itself is unknown. Change the viewpoint: if Aᵢ and A_j leave the same remainder with respect to d, then their difference is divisible by d. The converse is also true. So the condition is equivalent to "d divides every difference exactly".

It is enough to check differences against one reference number, for example A₁. If d divides both A₂ − A₁ and A₃ − A₁ exactly, then it also divides A₃ − A₂ exactly, because that difference is the difference of the two previous differences.

The largest d that divides all of them exactly is the GCD of all the differences.

Initial value 0. The GCD is computed step by step, and the correct initial value is 0 because fpb(0, x) = x. That initial value also handles the special case: if all the numbers are equal, all the differences are 0 and the result stays 0 — exactly what the problem asks for.

Walkthrough.

long long hasil = 0;
for (int i = 1; i < n; i++) {
    long long selisih = a[i] - a[0];
    if (selisih < 0) selisih = -selisih;
    hasil = fpb(hasil, selisih);
}

cout << hasil << "\n";

Tests.

Common mistakes.

• Starting hasil ("result") from 1, so the answer is always 1.
• Taking the GCD of the numbers themselves, not of their differences. For 5 11 17 that approach answers 1.
• Forgetting the absolute value when the reference is not the smallest number.

If you are still stuck

• Unsure whether to pick GCD or LCM → Chapter 15, section Problem patterns. "When do they repeat together" is LCM; "what is the largest number of groups" is GCD.
• The LCM answer becomes negative or strange → Chapter 15, the warning about the order of operations.
• You need a modular inverse but the modulus is not prime → Chapter 15, section The extended Euclidean algorithm.

The Euclidean algorithm is only four lines and is used in many problems; rewrite it from memory until you no longer need to think about it.