GCD and Euclidean Algorithm

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute gcd(a, b) using the iterative Euclidean Algorithm.
5
// Handles negative inputs; returns a nonnegative gcd.
6
long long gcd_ll(long long a, long long b) {
7
    a = llabs(a);
8
    b = llabs(b);
9
    while (b != 0) {
10
        long long r = a % b; // remainder
11
        a = b;
12
        b = r;
13
    }
14
    return a; // gcd(a, 0) = |a|
15
}
16
17
// Overflow-safe LCM. Returns {ok, value}.
18
// If a==0 or b==0, lcm is 0 by convention (for nonzero a,b). If overflow would occur, ok=false.
19
pair<bool, long long> lcm_ll(long long a, long long b) {
20
    if (a == 0 || b == 0) return {true, 0};
21
    long long g = gcd_ll(a, b);
22
    // Compute (a/g) * b in 128-bit to avoid overflow, then check bounds.
23
    __int128 t = (__int128)(a / g) * (__int128)b;
24
    if (t > LLONG_MAX || t < LLONG_MIN) return {false, 0};
25
    long long ans = (long long) (t >= 0 ? t : -t); // LCM is nonnegative
26
    return {true, ans};
27
}
28
29
int main() {
30
    ios::sync_with_stdio(false);
31
    cin.tie(nullptr);
32
33
    // Demo: read pairs and print gcd and lcm
34
    int q; 
35
    cout << "Enter number of test cases: ";
36
    if (!(cin >> q)) return 0;
37
    while (q--) {
38
        long long a, b; 
39
        cout << "Enter a and b: ";
40
        cin >> a >> b;
41
        long long g = gcd_ll(a, b);
42
        auto [ok, l] = lcm_ll(a, b);
43
        cout << "gcd(" << a << ", " << b << ") = " << g << '\n';
44
        if (ok) cout << "lcm(" << a << ", " << b << ") = " << l << '\n';
45
        else    cout << "lcm(" << a << ", " << b << ") overflows 64-bit range\n";
46
    }
47
    return 0;
48
}
49

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Recursive extended Euclidean Algorithm.
5
// Returns gcd(a,b) and finds x,y such that a*x + b*y = gcd(a,b).
6
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
7
    if (b == 0) {
8
        x = (a >= 0 ? 1 : -1); // ensure gcd nonnegative
9
        y = 0;
10
        return llabs(a);
11
    }
12
    long long x1, y1;
13
    long long g = ext_gcd(b, a % b, x1, y1);
14
    // Back-substitute: x = y1, y = x1 - floor(a/b) * y1
15
    x = y1;
16
    y = x1 - (a / b) * y1;
17
    return g;
18
}
19
20
// Computes modular inverse of a mod m if it exists.
21
// Returns pair {exists, inverse_in_[0,m-1]}.
22
pair<bool, long long> mod_inverse(long long a, long long m) {
23
    long long x, y;
24
    long long g = ext_gcd(a, m, x, y);
25
    if (g != 1) return {false, 0}; // inverse exists iff gcd(a,m)=1
26
    long long inv = (x % m + m) % m; // normalize to [0, m-1]
27
    return {true, inv};
28
}
29
30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
34
    cout << "Enter a and m to compute modular inverse of a mod m (q lines, end with EOF):\n";
35
    long long a, m;
36
    while (cin >> a >> m) {
37
        auto [ok, inv] = mod_inverse(a, m);
38
        if (!ok) {
39
            cout << "Inverse does not exist since gcd(" << a << ", " << m << ") != 1\n";
40
        } else {
41
            cout << "Inverse of " << a << " mod " << m << " is " << inv 
42
                 << " (check: " << ( (__int128)a * inv % m ) << ")\n";
43
        }
44
    }
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
5
    if (b == 0) { x = (a >= 0 ? 1 : -1); y = 0; return llabs(a); }
6
    long long x1, y1; long long g = ext_gcd(b, a % b, x1, y1);
7
    x = y1; y = x1 - (a / b) * y1; return g;
8
}
9
10
// Finds one solution to a*x + b*y = c. Returns {exists, x, y, g}.
11
struct Solution { bool ok; long long x, y, g; };
12
13
Solution solve_diophantine(long long a, long long b, long long c) {
14
    long long x0, y0; long long g = ext_gcd(a, b, x0, y0);
15
    if (c % g != 0) return {false, 0, 0, g};
16
    long long k = c / g;
17
    __int128 xx = (__int128)x0 * k;
18
    __int128 yy = (__int128)y0 * k;
19
    // Clamp back to 64-bit assuming results fit for given inputs.
20
    return {true, (long long)xx, (long long)yy, g};
21
}
22
23
// Shift solution (x, y) to make x >= 0 if possible.
24
// General solution: x = x0 + t*(b/g), y = y0 - t*(a/g).
25
void shift_to_nonneg_x(long long a, long long b, long long g, long long &x, long long &y) {
26
    long long dx = b / g;
27
    long long dy = a / g;
28
    if (dx == 0) return; // then a!=0,b==0; x fixed
29
    // We need x + t*dx >= 0 -> t >= (-x + dx - 1) // dx (ceiling division)
30
    auto ceil_div = [](long long p, long long q) {
31
        // ceil(p/q) for integers with q>0
32
        if (q < 0) p = -p, q = -q;
33
        if (p >= 0) return (p + q - 1) / q;
34
        else return p / q; // trunc toward 0 works as ceil when p<0
35
    };
36
    long long t = ceil_div(-x, dx);
37
    x += t * dx;
38
    y -= t * dy;
39
}
40
41
int main() {
42
    ios::sync_with_stdio(false);
43
    cin.tie(nullptr);
44
45
    cout << "Solve ax + by = c (enter a b c, one per line, EOF to stop):\n";
46
    long long a, b, c;
47
    while (cin >> a >> b >> c) {
48
        Solution sol = solve_diophantine(a, b, c);
49
        if (!sol.ok) {
50
            cout << "No integer solution because gcd(" << a << ", " << b << ") = " << sol.g 
51
                 << " does not divide " << c << "\n";
52
            continue;
53
        }
54
        long long x = sol.x, y = sol.y;
55
        cout << "One solution: x = " << x << ", y = " << y << " (check: "
56
             << ( (__int128)a * x + (__int128)b * y ) << ")\n";
57
        // Optionally find a solution with x >= 0
58
        shift_to_nonneg_x(a, b, sol.g, x, y);
59
        cout << "Shifted solution with x >= 0: x = " << x << ", y = " << y << "\n";
60
    }
61
    return 0;
62
}
63

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
long long gcd_ll(long long a, long long b) {
5
    a = llabs(a); b = llabs(b);
6
    while (b) { long long r = a % b; a = b; b = r; }
7
    return a;
8
}
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    cout << "Enter n: ";
15
    int n; if (!(cin >> n)) return 0;
16
    vector<long long> a(n+1);
17
    cout << "Enter array of n integers: ";
18
    for (int i = 1; i <= n; ++i) cin >> a[i];
19
20
    // Build prefix and suffix gcd arrays in O(n)
21
    vector<long long> pre(n+2, 0), suf(n+2, 0);
22
    for (int i = 1; i <= n; ++i) pre[i] = gcd_ll(pre[i-1], a[i]);
23
    for (int i = n; i >= 1; --i) suf[i] = gcd_ll(suf[i+1], a[i]);
24
25
    cout << "Enter number of queries q: ";
26
    int q; cin >> q;
27
    cout << "Each query gives an index i (1-based); output gcd of all elements except a[i].\n";
28
    while (q--) {
29
        int i; cin >> i;
30
        long long ans = gcd_ll(pre[i-1], suf[i+1]);
31
        cout << ans << '\n';
32
    }
33
34
    // Example: gcd of entire array is pre[n] (or suf[1])
35
    // Example: gcd of subarray [L..R] could be answered with a sparse table (not shown here).
36
37
    return 0;
38
}
39