Tìm x và y thỏa mãn ax + by = n trong C++

Trong bài toán này, chúng ta được cho ba giá trị nguyên a, b và n. Nhiệm vụ là tìm x và y thỏa mãn ax + by = n.

Ví dụ minh họa

Input: a = 4, b = 1, n = 5 Output: x = 1, y = 1

Phương pháp giải

Giải pháp đơn giản là tìm giá trị từ 0 đến n thỏa mãn phương trình. Chúng ta sử dụng dạng biến đổi của phương trình:

x = (n - by)/a
y = (n - ax)/b

Nếu tìm được giá trị thỏa mãn, in ra kết quả, ngược lại in "không có nghiệm".

Ví dụ chương trình

#include <iostream> 
using namespace std; 

void findSolution(int a, int b, int n){
    for (int i = 0; i * a <= n; i++) {
        if ((n - (i * a)) % b == 0) {
            cout << i << " và " << (n - (i * a)) / b;
            return;
        }
    }
    cout << "Không có nghiệm";
}

int main(){
    int a = 2, b = 3, n = 7;
    cout << "Giá trị x và y cho phương trình 'ax + by = n' là: ";
    findSolution(a, b, n);
    return 0;
}

Kết quả

Giá trị x và y cho phương trình 'ax + by = n' là 2 và 1