1. GCD and LCM Algorithms

1.1 Euclidean Algorithm for GCD

The Euclidean algorithm computes gcd(a, b) by repeatedly replacing the larger number by its remainder when divided by the smaller:

  1. While b != 0:
    • r = a % b
    • a = b
    • b = r
  2. When b == 0, a is the GCD.

Time complexity: O(log min(a, b)).
Memory complexity: O(1) (only a few integer variables).

1.2 Computing LCM via GCD

Once you have g = gcd(a, b), you can compute lcm(a, b) = |a * b| / g. This also runs in O(log min(a, b)) time and O(1) space.

2. Easy Problems

2.1 Problem: Compute GCD of Two Numbers

Description: Given two positive integers, output their greatest common divisor. 

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << endl;
    return 0;
}

2.2 Problem: Compute LCM of Two Numbers

Description: Given two positive integers, output their least common multiple. 

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long long lcm(int a, int b) {
    return (long long)a / gcd(a, b) * b;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << lcm(x, y) << endl;
    return 0;
}

3. Intermediate Problems

3.1 Problem: Simplify a Fraction

Description: Given numerator p and denominator q, reduce the fraction p/q to lowest terms. 

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int p, q;
    cin >> p >> q;
    int g = gcd(abs(p), abs(q));
    p /= g;
    q /= g;
    if (q < 0) { // keep denominator positive
        p = -p;
        q = -q;
    }
    cout << p << "/" << q << endl;
    return 0;
}

3.2 Problem: GCD of an Array of Numbers

Description: Given an array of n positive integers, find the GCD of the entire array. 

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int result = a[0];
    for (int i = 1; i < n; ++i) {
        result = gcd(result, a[i]);
    }
    cout << result << endl;
    return 0;
}

4. Hard Problem

4.1 Problem: Solve the Linear Diophantine Equation ax + by = c

Description: Given integers a, b, and c, determine whether there exist integers x and y satisfying a·x + b·y = c, and if so, find one solution.

Approach:
Use the extended Euclidean algorithm to compute g = gcd(a, b) and coefficients x0, y0 such that a·x0 + b·y0 = g. A solution to a·x + b·y = c exists iff g divides c. Then multiply (x0, y0) by c/g to get one particular solution. 

#include <iostream>
#include <tuple>
using namespace std;

// returns (g, x, y) such that a*x + b*y = g = gcd(a, b)
tuple<int,int,int> extended_gcd(int a, int b) {
    if (b == 0) return {a, 1, 0};
    int g, x1, y1;
    tie(g, x1, y1) = extended_gcd(b, a % b);
    int x = y1;
    int y = x1 - (a / b) * y1;
    return {g, x, y};
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int g, x0, y0;
    tie(g, x0, y0) = extended_gcd(abs(a), abs(b));
    if (c % g != 0) {
        cout << "No solution" << endl;
    } else {
        // scale the basic solution
        x0 *= c / g;
        y0 *= c / g;
        // adjust signs if a or b were negative
        if (a < 0) x0 = -x0;
        if (b < 0) y0 = -y0;
        cout << "One solution: x = " << x0
             << ", y = " << y0 << endl;
    }
    return 0;
}