Tìm k sao cho modulo với mọi phần tử mảng bằng nhau C++

Cho mảng, tìm tất cả số nguyên k > 0 sao cho arr[i] % k giống nhau ∀ i.

Quan sát quan trọng

Nếu arr[i] % k = arr[j] % k thì (arr[i] - arr[j]) % k = 0. Do đó k phải là ước của mọi hiệu arr[i] - arr[j].

→ k là ước của GCD(|arr[i] - arr[0]|) với mọi i.

Thuật toán

• Sắp xếp mảng.
• Tính g = GCD(arr[i] - arr[0]) cho i=1..n-1.
• Tìm tất cả ước của g (k > 0).

Chương trình C++

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

int main() {
    vector arr = {12, 22, 32};
    sort(arr.begin(), arr.end());
    
    int g = 0;
    for (int i = 1; i < (int)arr.size(); i++)
        g = gcd(g, arr[i] - arr[0]);
    
    cout << "GCD of differences: " << g << "\n";
    cout << "Cac gia tri k: ";
    for (int i = 1; i*i <= g; i++) {
        if (g % i == 0) {
            cout << i << " ";
            if (i != g/i) cout << g/i << " ";
        }
    }
    return 0;
}

Kết quả

GCD of differences: 10
Cac gia tri k: 1 10 2 5 

Kiểm tra: 12%1=0, 22%1=0, 32%1=0 ✓ | 12%2=0, 22%2=0, 32%2=0 ✓ | 12%5=2, 22%5=2, 32%5=2 ✓ | 12%10=2, 22%10=2, 32%10=2 ✓