Giá trị nguyên dương nhỏ nhất của X cho A, B cho trước trong X = P*A + Q*B trong C++

Đề bài

Cho giá trị A và B, tìm giá trị nguyên dương nhỏ nhất của X có thể đạt được trong phương trình X = P*A + Q*B, ở đây P và Q có thể là 0 hoặc bất kỳ số nguyên dương hoặc âm nào.

Ví dụ

Nếu A = 2 và B = 4 thì câu trả lời sẽ là 2.

Thuật toán

• Cần tìm P và Q sao cho P*A > P*B và P*A - P*B là số nguyên dương nhỏ nhất.
• Bài toán này dễ dàng giải quyết bằng cách tính GCD của cả hai số.

Ví dụ

#include <iostream>
using namespace std;
int getGcd(int a, int b) {
    if (a == 0) {
        return b;
    }
    return getGcd(b % a, a);
}
int main() {
    cout << "Đáp án = " << getGcd(2, 4) << endl;
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Đáp án = 2