#include <iostream>
#include <vector>
#include <cstdlib> // 为了abs函数
using namespace std;

// 最大公约数（欧几里得算法）
int gcd(int a, int b) {
    while (b) {
        int t = a % b;  // 余数
        a = b;          // 更新a为原b
        b = t;          // 更新b为余数
    }
    return a;
}

// 最小公倍数：先除后乘防止溢出
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

// 数组的最大公约数
int gcd_array(const vector<int> &arr) {
    int res = arr[0];  // 初始化为第一个元素
    for (int i = 1; i < arr.size(); i++) {
        res = gcd(res, arr[i]);  // 依次两两计算
    }
    return res;
}

// 数组的最小公倍数
int lcm_array(const vector<int> &arr) {
    int res = arr[0];  // 初始化为第一个元素
    for (int i = 1; i < arr.size(); i++) {
        res = lcm(res, arr[i]);  // 依次两两计算
    }
    return res;
}

// 分数结构体
struct Fraction {
    int num;  // 分子
    int den;  // 分母
};

// 分数化简
Fraction reduce_fraction(Fraction f) {
    int g = gcd(abs(f.num), abs(f.den));  // 取绝对值求gcd
    f.num /= g;  // 分子除以gcd
    f.den /= g;  // 分母除以gcd
    // 通常分母为正
    if (f.den < 0) {
        f.num = -f.num;
        f.den = -f.den;
    }
    return f;
}

// 分数加法
Fraction add_fraction(Fraction a, Fraction b) {
    // 通分：分母为lcm
    int common_den = lcm(a.den, b.den);  // 公分母
    int new_num = a.num * (common_den / a.den) + b.num * (common_den / b.den);
    Fraction result = {new_num, common_den};
    return reduce_fraction(result);  // 最后约分
}

int main() {
    // 1. 两个数的gcd和lcm
    int x = 48;   // 第一个数
    int y = 36;   // 第二个数
    cout << "gcd(" << x << "," << y << ") = " << gcd(x, y) << endl;
    cout << "lcm(" << x << "," << y << ") = " << lcm(x, y) << endl;

    // 2. 数组的gcd和lcm
    vector<int> numbers = {12, 18, 24};  // 三个数
    cout << "数组[12,18,24]的gcd = " << gcd_array(numbers) << endl;
    cout << "数组[12,18,24]的lcm = " << lcm_array(numbers) << endl;

    // 3. 分数化简
    Fraction frac = {48, 36};  // 待化简的分数
    Fraction reduced = reduce_fraction(frac);
    cout << "分数48/36化简为 " << reduced.num << "/" << reduced.den << endl;

    // 4. 分数加法
    Fraction a = {1, 6};   // 第一个分数 1/6
    Fraction b = {1, 8};   // 第二个分数 1/8
    Fraction sum = add_fraction(a, b);
    cout << "1/6 + 1/8 = " << sum.num << "/" << sum.den << endl;  // 7/24

    return 0;
}

import math

def gcd(a, b):
    """欧几里得算法求最大公约数"""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """最小公倍数（先除后乘）"""
    return a // gcd(a, b) * b

def gcd_array(arr):
    """数组的gcd"""
    res = arr[0]  # 第一个数
    for num in arr[1:]:
        res = gcd(res, num)  # 两两计算
    return res

def lcm_array(arr):
    """数组的lcm"""
    res = arr[0]  # 第一个数
    for num in arr[1:]:
        res = lcm(res, num)  # 两两计算
    return res

def reduce_fraction(num, den):
    """化简分数，返回(分子,分母)"""
    g = gcd(abs(num), abs(den))  # 取绝对值求gcd
    num //= g  # 分子除以gcd
    den //= g  # 分母除以gcd
    if den < 0:  # 分母调为正
        num = -num
        den = -den
    return num, den

def add_fraction(a_num, a_den, b_num, b_den):
    """分数加法，a_num/a_den + b_num/b_den"""
    common_den = lcm(a_den, b_den)  # 公分母
    new_num = a_num * (common_den // a_den) + b_num * (common_den // b_den)
    return reduce_fraction(new_num, common_den)

# 测试
x, y = 48, 36  # 两个示例数
print(f"gcd({x},{y}) = {gcd(x, y)}")
print(f"lcm({x},{y}) = {lcm(x, y)}")

numbers = [12, 18, 24]  # 数组
print(f"数组{numbers}的gcd = {gcd_array(numbers)}")
print(f"数组{numbers}的lcm = {lcm_array(numbers)}")

num, den = reduce_fraction(48, 36)
print(f"分数48/36化简为 {num}/{den}")

s_num, s_den = add_fraction(1, 6, 1, 8)
print(f"1/6 + 1/8 = {s_num}/{s_den}")