Chương trình C/C++ số nghiệm phương trình đồng dư

Phương trình đồng dư: B ≡ A (mod X). Nghĩa là B đồng dư với A modulo X. Ví dụ: 21 ≡ 5 (mod 4) vì 21%4=1 và 5%4=1.

Cho A, B nguyên, tìm số giá trị X thỏa mãn A mod X = B.

Input: A = 26, B = 2 Output: X can take 6 values

Giải thích

X ∈ {3,4,6,8,12,24} vì 26 mod các giá trị này đều = 2.

Điều kiện: nếu A=B thì vô số nghiệm X > A. Nếu A<B thì vô nghiệm. Nếu A>B: A = X*Y + B => A-B = X*Y. Vậy X là ước của (A-B) và X > B. Số nghiệm = số ước của (A-B) lớn hơn B.

Ví dụ

#include <iostream>
#include <math.h>
using namespace std;

int Divisors(int A, int B) {
    int N = (A - B);
    int D = 0;
    for (int i = 1; i <= sqrt(N); i++) {
        if ((N % i) == 0) {
            if (i > B) D++;
            if ((N / i) != i && (N / i) > B) D++;
        }
    }
    return D;
}

int PossibleWaysUtil(int A, int B) {
    if (A == B) return -1;
    if (A < B) return 0;
    return Divisors(A, B);
}

int main() {
    int A = 26, B = 2;
    int Sol = PossibleWaysUtil(A, B);
    if (Sol == -1) {
        cout << " X can take Infinitely many values greater than " << A << "\n";
    } else {
        cout << " X can take " << Sol << " values\n";
        return 0;
    }
}