Tìm k sao cho modulo với mọi phần tử mảng cho cùng kết quả C++

Giới thiệu

Cho mảng số nguyên, tìm tất cả số k > 0 sao cho: a₁ % k = a₂ % k = ... = aₙ % k.

Ý tưởng toán học

Nếu x % k = y % k với x > y, thì (x - y) % k = 0 → k là ước của (x - y).
Với mảng, k phải là ước chung của tất cả hiệu cặp → k là ước của (max - min).

Các bước

1. Sắp xếp mảng.
2. Tính d = max - min.
3. Nếu d = 0 → tất cả phần tử bằng nhau → vô hạn k.
4. Tìm tất cả ước của d.
5. Kiểm tra từng ước: nếu modulo với mọi phần tử cho cùng kết quả → là k hợp lệ.

Mã nguồn ví dụ

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

void findNumbers(int arr[], int n) {
    sort(arr, arr + n);
    int d = arr[n - 1] - arr[0];
    if (d == 0) { cout << "Vô số k"; return; }
    vector<int> divisors;
    for (int i = 1; i * i <= d; i++) {
        if (d % i == 0) {
            divisors.push_back(i);
            if (i != d / i) divisors.push_back(d / i);
        }
    }
    for (int k : divisors) {
        int temp = arr[0] % k;
        bool ok = true;
        for (int j = 1; j < n; j++)
            if (arr[j] % k != temp) { ok = false; break; }
        if (ok) cout << k << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 4, 2};
    findNumbers(arr, 3);
    return 0;
}

Kết quả đầu ra

1 2

Kết luận

Với mảng {10, 4, 2}: max=10, min=2, d=8. Ước của 8: 1,2,4,8. Chỉ 1 và 2 cho cùng modulo (0). Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.