普及组最大公因数与最小公倍数专题训练

题目1：基础GCD计算（简单）

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int a, b;
    cin >> a >> b;
    
    int result = gcd(a, b);
    cout << a << "和" << b << "的最大公约数是" << result << endl;
    
    return 0;
}

判断题

1. 欧几里得算法基于gcd(a, b) = gcd(b, a mod b)的原理。 ( )
2. 当a和b都是素数时，它们的最大公约数一定是1。 ( )
3. 如果a能被b整除，那么gcd(a, b) = b。 ( )

选择题 4. 输入a=56, b=98时，程序的输出是（ ）。 A. 2 B. 7 C. 14 D. 28

5. 这个算法的时间复杂度是（ ）。 A. O(1) B. O(log min(a, b)) C. O(min(a, b)) D. O(a + b)

题目2：基础LCM计算（简单）

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

int main() {
    int a, b;
    cin >> a >> b;
    
    int result = lcm(a, b);
    cout << a << "和" << b << "的最小公倍数是" << result << endl;
    
    return 0;
}

判断题

1. 最小公倍数可以通过两数乘积除以最大公约数得到。 ( )
2. 对于任意两个正整数a和b，lcm(a, b) ≥ max(a, b)。 ( )
3. 如果a和b互质，那么lcm(a, b) = a × b。 ( )

选择题 4. 输入a=15, b=20时，程序的输出是（ ）。 A. 5 B. 30 C. 60 D. 300

5. 如果a和b都很大，直接计算a×b可能会导致整数溢出。为了避免这种情况，可以改为（ ）。 A. lcm(a, b) = a / gcd(a, b) * b B. lcm(a, b) = b / gcd(a, b) * a C. 两者都可以 D. 无法避免

题目3：多个数的GCD和LCM（中等）

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

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

int gcd_vector(vector<int>& nums) {
    int result = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        result = gcd(result, nums[i]);
    }
    return result;
}

int lcm_vector(vector<int>& nums) {
    int result = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        result = lcm(result, nums[i]);
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    int gcd_result = gcd_vector(nums);
    int lcm_result = lcm_vector(nums);
    
    cout << "最大公约数: " << gcd_result << endl;
    cout << "最小公倍数: " << lcm_result << endl;
    
    return 0;
}

判断题

1. 多个数的最大公约数可以通过两两计算得到。 ( )
2. 多个数的最小公倍数可以通过两两计算得到。 ( )
3. 对于任意一组正整数，它们的最大公约数一定不大于最小公倍数。 ( )

选择题 4. 输入n=3, nums=[12, 18, 24]时，最大公约数的输出是（ ）。 A. 2 B. 4 C. 6 D. 8

5. 输入n=3, nums=[4, 6, 8]时，最小公倍数的输出是（ ）。 A. 12 B. 24 C. 32 D. 48

题目4：GCD应用-分数化简（中等偏难）

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

struct Fraction {
    int numerator;
    int denominator;
    
    Fraction(int num, int den) : numerator(num), denominator(den) {}
    
    void simplify() {
        int common = gcd(numerator, denominator);
        numerator /= common;
        denominator /= common;
    }
    
    Fraction add(const Fraction& other) {
        int new_num = numerator * other.denominator + other.numerator * denominator;
        int new_den = denominator * other.denominator;
        Fraction result(new_num, new_den);
        result.simplify();
        return result;
    }
    
    Fraction multiply(const Fraction& other) {
        int new_num = numerator * other.numerator;
        int new_den = denominator * other.denominator;
        Fraction result(new_num, new_den);
        result.simplify();
        return result;
    }
    
    void print() {
        cout << numerator << "/" << denominator;
    }
};

int main() {
    int a, b, c, d;
    char op;
    
    cin >> a >> b >> op >> c >> d;
    
    Fraction f1(a, b);
    Fraction f2(c, d);
    Fraction result(0, 1);
    
    if (op == '+') {
        result = f1.add(f2);
    } else if (op == '*') {
        result = f1.multiply(f2);
    }
    
    f1.print();
    cout << " " << op << " ";
    f2.print();
    cout << " = ";
    result.print();
    cout << endl;
    
    return 0;
}

判断题

1. 分数相加时，需要先通分再相加。 ( )
2. 分数相乘时，直接分子乘分子，分母乘分母。 ( )
3. 分数化简时，需要找到分子和分母的最大公约数。 ( )

选择题 4. 输入"1/2 + 1/3"时，程序的输出是（ ）。 A. 2/5 B. 2/6 C. 3/6 D. 5/6

5. 输入"2/3 * 3/4"时，程序的输出是（ ）。 A. 6/12 B. 1/2 C. 2/3 D. 3/4

题目5：GCD与数论结合-线性同余方程（最难）

#include <iostream>
using namespace std;

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool solve_linear_congruence(int a, int b, int m, int& x) {
    int x0, y0;
    int d = gcd(a, m, x0, y0);
    
    if (b % d != 0) {
        return false;
    }
    
    int x1 = (x0 * (b / d)) % m;
    if (x1 < 0) {
        x1 += m;
    }
    
    x = x1;
    return true;
}

int main() {
    int a, b, m;
    cin >> a >> b >> m;
    
    int x;
    if (solve_linear_congruence(a, b, m, x)) {
        cout << "方程 " << a << "x ≡ " << b << " (mod " << m << ") 的解是 x ≡ " << x << " (mod " << m << ")" << endl;
    } else {
        cout << "方程 " << a << "x ≡ " << b << " (mod " << m << ") 无解" << endl;
    }
    
    return 0;
}

判断题

1. 扩展欧几里得算法可以求解ax + by = gcd(a, b)。 ( )
2. 线性同余方程ax ≡ b (mod m)有解当且仅当gcd(a, m)能整除b。 ( )
3. 如果线性同余方程有解，那么它有无穷多个解。 ( )

选择题 4. 对于方程3x ≡ 2 (mod 5)，解是（ ）。 A. x ≡ 1 (mod 5) B. x ≡ 2 (mod 5) C. x ≡ 3 (mod 5) D. x ≡ 4 (mod 5)

5. 对于方程4x ≡ 2 (mod 6)，解的情况是（ ）。 A. 有唯一解 B. 有两个解 C. 有多个解 D. 无解