Đếm các cặp chia hết nhau trong mảng C++

Cho một mảng số nguyên, nhiệm vụ là đếm số cặp (i,j) với i < j sao cho một phần tử chia hết cho phần tử kia (arr[i] % arr[j] == 0 hoặc arr[j] % arr[i] == 0).

Ví dụ

Input - arr[] = {1, 2, 3, 6} Output - count is 4

Giải thích - Các cặp: (1,2), (1,3), (1,6), (3,6). 1 chia hết mọi số, 3 chia hết 6.

Input - arr[] = {2, 5, 10} Output - count is 2

Giải thích - Các cặp: (2,10), (5,10).

Phương pháp tiếp cận

• Duyệt qua tất cả các cặp (i,j) với i < j
• Kiểm tra điều kiện arr[i] % arr[j] == 0 hoặc arr[j] % arr[i] == 0
• Tăng biến đếm nếu thỏa mãn
• Độ phức tạp O(n²)

Ví dụ code C++

#include <iostream>
using namespace std;

int divisibles(int a[], int size) {
    int result = 0;
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (a[i] % a[j] == 0 || a[j] % a[i] == 0) {
                result++;
            }
        }
    }
    return result;
}

int main() {
    int a[] = {1, 4, 7, 8, 9};
    int size = sizeof(a) / sizeof(a[0]);
    cout << "count is " << divisibles(a, size);
    return 0;
}

Kết quả

count is 5