Tìm số nghiệm của phương trình đồng dư bằng C++

Trong bài viết này, chúng ta sẽ giải thích về nghiệm của phương trình đồng dư và viết chương trình tìm số nghiệm. Ví dụ cơ bản:

Input : X = 30, Y = 2 Output : 4, 7, 14, 28
Giải thích: 30 mod 4 = 2, 30 mod 7 = 2, 30 mod 14 = 2, 30 mod 28 = 2

Mọi số nguyên cho phép chia X dư Y là một nghiệm. Ta nhận thấy: X mod m = Y ⟺ m chia hết (X - Y) và m > Y.

Phương pháp giải quyết

Ta đếm số ước của N = X - Y mà lớn hơn Y. Các trường hợp đặc biệt:

• X == Y: vô số nghiệm (bất kỳ m > X)
• X < Y: không có nghiệm (dư không thể lớn hơn số bị chia)
• X > Y: đếm ước của X - Y lớn hơn Y

Mã nguồn C++

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

int numberofdivisor(int X, int Y) {
    int N = (X - Y);
    int noOfDivisors = 1; // tự thân N cũng là ước
    for (int i = 1; i <= N / 2; i++) {
        if ((N % i) == 0) {
            if (i > Y)
                noOfDivisors++;
        }
    }
    return noOfDivisors;
}

void numberofsolutions(int X, int Y) {
    int noOfSolutions;
    if (X == Y)
        noOfSolutions = -1;
    else if (X < Y)
        noOfSolutions = 0;
    else
        noOfSolutions = numberofdivisor(X, Y);

    if (noOfSolutions == -1) {
        cout << "X có thể lấy vô số giá trị lớn hơn " << X << "\n";
    } else {
        cout << "Số nghiệm = " << noOfSolutions;
    }
}

int main() {
    int X, Y;
    cin >> X >> Y;
    numberofsolutions(X, Y);
    return 0;
}

Kết quả

X có thể lấy vô số giá trị lớn hơn 0

Số nghiệm = 2

Giải thích mã nguồn

• main(): nhập X, Y và gọi numberofsolutions().
• numberofsolutions(): kiểm tra điều kiện X và Y, gọi hàm đếm ước.
• numberofdivisor(): duyệt từ 1 đến (X-Y)/2, đếm các ước lớn hơn Y.

Kết luận

Nghiệm của phương trình đồng dư X mod m = Y là các ước của X - Y lớn hơn Y. Chương trình C++ đã được trình bày đầy đủ, có thể chuyển sang C, Java, Python dễ dàng.