gcd_lcm.cpp

/*
GCD & LCM (Greatest Common Divisor & Least Common Multiple)
Mathematical Foundation: 
Euclidean Algorithm: gcd(a,b) = gcd(b, a%b), gcd(a,0) = a
LCM: lcm(a,b) = (a*b) / gcd(a,b)
Extended Euclidean: ax + by = gcd(a,b)
Time: O(log(min(a,b)))
*/

#include <bits/stdc++.h>
using namespace std;

// GCD - Euclidean Algorithm
// Related LeetCode Problems:
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
// 914. X of a Kind in a Deck of Cards
// https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 1952. Three Divisors
// https://leetcode.com/problems/three-divisors/
// 1370. Increasing Decreasing String
// https://leetcode.com/problems/increasing-decreasing-string/
long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

// LCM using GCD
// Related LeetCode Problems:
// 2413. Smallest Even Multiple
// https://leetcode.com/problems/smallest-even-multiple/
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
// 914. X of a Kind in a Deck of Cards
// https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
// 2001. Number of Pairs of Interchangeable Rectangles
// https://leetcode.com/problems/number-of-pairs-of-interchangeable-rectangles/
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

// Extended Euclidean Algorithm
// Returns gcd(a,b) and finds x,y such that ax + by = gcd(a,b)
// Related LeetCode Problems:
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
// 2607. Make K-Subarray Sums Equal
// https://leetcode.com/problems/make-k-subarray-sums-equal/
long long extgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular Inverse using Extended Euclidean
// Related LeetCode Problems:
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
// 2607. Make K-Subarray Sums Equal
// https://leetcode.com/problems/make-k-subarray-sums-equal/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
long long modinv(long long a, long long m) {
    long long x, y;
    long long g = extgcd(a, m, x, y);
    return g == 1 ? (x % m + m) % m : -1;
}

// GCD of Array
// LeetCode: 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// Related:
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
// 914. X of a Kind in a Deck of Cards
// https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
// 1952. Three Divisors
// https://leetcode.com/problems/three-divisors/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
long long gcdArray(vector<long long>& arr) {
    long long result = arr[0];
    for (int i = 1; i < arr.size(); i++)
        result = gcd(result, arr[i]);
    return result;
}

// LCM of Array
// Related LeetCode Problems:
// 2413. Smallest Even Multiple
// https://leetcode.com/problems/smallest-even-multiple/
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 2001. Number of Pairs of Interchangeable Rectangles
// https://leetcode.com/problems/number-of-pairs-of-interchangeable-rectangles/
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
// 914. X of a Kind in a Deck of Cards
// https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
long long lcmArray(vector<long long>& arr) {
    long long result = arr[0];
    for (int i = 1; i < arr.size(); i++)
        result = lcm(result, arr[i]);
    return result;
}

// Binary GCD (Stein's Algorithm) - for very large numbers
// Related LeetCode Problems:
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
// 914. X of a Kind in a Deck of Cards
// https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
long long binaryGCD(long long a, long long b) {
    if (a == 0) return b;
    if (b == 0) return a;
    
    int k = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1; b >>= 1; k++;
    }
    
    while ((a & 1) == 0) a >>= 1;
    
    do {
        while ((b & 1) == 0) b >>= 1;
        if (a > b) swap(a, b);
        b -= a;
    } while (b);
    
    return a << k;
}

// Coprime Check
// Related LeetCode Problems:
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
// 914. X of a Kind in a Deck of Cards
// https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
// 1952. Three Divisors
// https://leetcode.com/problems/three-divisors/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
bool areCoprime(long long a, long long b) {
    return gcd(a, b) == 1;
}

// Euler's Totient Function φ(n)
// Related LeetCode Problems:
// 1952. Three Divisors
// https://leetcode.com/problems/three-divisors/
// 1819. Number of Different Subsequences GCDs
// https://leetcode.com/problems/number-of-different-subsequences-gcds/
// 1979. Find Greatest Common Divisor of Array
// https://leetcode.com/problems/find-greatest-common-divisor-of-array/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
long long phi(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

// Linear Diophantine Equation: ax + by = c
// Returns true if solution exists
// Related LeetCode Problems:
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
// 2607. Make K-Subarray Sums Equal
// https://leetcode.com/problems/make-k-subarray-sums-equal/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
bool linearDiophantine(long long a, long long b, long long c, long long& x, long long& y) {
    long long g = extgcd(abs(a), abs(b), x, y);
    if (c % g != 0) return false;
    
    x *= c / g;
    y *= c / g;
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return true;
}

// Chinese Remainder Theorem
// Solve: x ≡ r[i] (mod m[i]) for all i
// Related LeetCode Problems:
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// 2607. Make K-Subarray Sums Equal
// https://leetcode.com/problems/make-k-subarray-sums-equal/
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
long long crt(vector<long long>& r, vector<long long>& m) {
    long long M = 1, result = 0;
    for (long long mod : m) M *= mod;
    
    for (int i = 0; i < m.size(); i++) {
        long long Mi = M / m[i];
        long long yi = modinv(Mi, m[i]);
        result = (result + r[i] * Mi % M * yi % M) % M;
    }
    return (result + M) % M;
}