Đếm cặp (i,j) có một số chia hết cho số kia trong mảng C++

Cho mảng N phần tử. Đếm số cặp chỉ số (i,j) với i ≠ j sao cho arr[i] chia hết cho arr[j] HOẶC arr[j] chia hết cho arr[i].

Ví dụ minh họa

Ví dụ 1:

• Input: Arr = {2, 4, 3, 6}, N = 4
• Output: 3
• Giải thích: (2,4): 4%2=0; (2,6): 6%2=0; (3,6): 6%3=0.

Ví dụ 2:

• Input: Arr = {2, 5, 7, 9, 11}, N = 5
• Output: 0
• Giải thích: Không có cặp nào chia hết nhau.

Mã nguồn C++ (Vét cạn O(n²))

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

int countPairs(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] % arr[j] == 0 || arr[j] % arr[i] == 0) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {2, 3, 4, 5, 6};
    int len = sizeof(Arr) / sizeof(Arr[0]);
    cout << "So cap chia het nhau: " << countPairs(Arr, len);
    return 0;
}

Kết quả chạy chương trình

So cap chia het nhau: 3

Tối ưu hóa O(n log n) - Sử dụng tần suất

Với giá trị phần tử ≤ M (ví dụ 10⁵):

1. Đếm tần suất freq[x] của mỗi giá trị.
2. Với mỗi giá trị x có freq[x] > 0, duyệt các bội số của x (2x, 3x, ... ≤ M).
3. Cộng freq[x] × freq[k×x] vào kết quả.
4. Xử lý riêng cặp (x,x): cộng C(freq[x], 2).

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

long long countPairsOptimized(vector& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    vector freq(maxVal + 1, 0);
    for (int x : arr) freq[x]++;
    
    long long count = 0;
    for (int x = 1; x <= maxVal; x++) {
        if (freq[x] == 0) continue;
        // Cặp (x, x)
        count += 1LL * freq[x] * (freq[x] - 1) / 2;
        // Cặp (x, k*x) với k >= 2
        for (int k = 2; k * x <= maxVal; k++) {
            if (freq[k * x] > 0) {
                count += 1LL * freq[x] * freq[k * x];
            }
        }
    }
    return count;
}

Độ phức tạp

M = giá trị lớn nhất trong mảng. Phù hợp khi M ≤ 10⁵-10⁶.