Đếm cặp trong mảng có tích tồn tại trong mảng trong C++

Giới thiệu

Cho mảng số nguyên, đếm số cặp (i, j) với i < j sao cho tích arr[i] * arr[j] cũng xuất hiện trong mảng.

Ví dụ

arr = [6,2,3,1,5,10] → Các cặp: (2,3)=6, (6,1)=6, (3,1)=3, (2,5)=10, (1,5)=5, (2,1)=2, (1,10)=10 → Kết quả: 7

Các cách tiếp cận

Cách 1: Naive O(n³)

Ba vòng lặp: chọn cặp, tính tích, tìm tích trong mảng.

Cách 2: Hiệu quả O(n²) dùng unordered_set

Đưa tất cả phần tử vào set. Duyệt cặp (i,j), kiểm tra tích có trong set không.

Ví dụ triển khai (C++)

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

// Cách 1: Naive
int countProductPairsNaive(vector<int> arr) {
    int count = 0, n = arr.size();
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            int prod = arr[i] * arr[j];
            for (int k = 0; k < n; k++)
                if (arr[k] == prod) { count++; break; }
        }
    return count;
}

// Cách 2: Hiệu quả với unordered_set
int countProductPairsFast(vector<int> arr) {
    unordered_set<int> s(arr.begin(), arr.end());
    int count = 0, n = arr.size();
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (s.count(arr[i] * arr[j])) count++;
    return count;
}

int main() {
    vector<int> arr = {6, 2, 3, 1, 5, 10};
    cout << "Naive: " << countProductPairsNaive(arr) << endl; // 7
    cout << "Fast: " << countProductPairsFast(arr) << endl;  // 7
    return 0;
}

Đầu vào

[6,2,3,1,5,10]