Đếm bộ tư (tuple) có tích bằng nhau trong mảng C++

Cho một mảng các số nguyên phân biệt. Nhiệm vụ là đếm tổng số bộ tư (a, b, c, d) sao cho tích của hai cặp bằng nhau: a × b = c × d. Ví dụ:

Đầu vào 1:

arr[] = {2, 4, 6, 3}

Đầu ra:

8

Giải thích: Có 8 bộ tư thỏa mãn: (2,6,3,4), (2,6,4,3), (6,2,3,4), (6,2,4,3), (3,4,2,6), (4,3,2,6), (3,4,6,2), (4,3,6,2). Trong đó 2×6 = 3×4 = 12.

Phương pháp giải quyết

Ý tưởng: sử dụng bảng băm (hashmap) để lưu tần suất xuất hiện của từng tích cặp số. Duyệt qua tất cả các cặp (i, j) với i < j, tính tích và tăng đếm. Với mỗi tích xuất hiện freq lần, số cách chọn 2 cặp khác nhau là freq * (freq - 1) / 2. Mỗi cặp có 2 phần tử, 2 cặp cho 4 phần tử, có 8 hoán vị (4! / (2!2!) × 2! × 2! = 8). Do đó tổng bộ tư = tổng trên tất cả tích của freq * (freq - 1) / 2 * 8.

• Nhập mảng và kích thước.
• Hàm countTuples(int *arr, int n) trả về số bộ tư.
• Duyệt cặp, lưu tích vào map.
• Duyệt map, cộng dồn kết quả theo công thức.

Ví dụ mã nguồn

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

int countTuples(int *arr, int n) {
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            mp[arr[i] * arr[j]]++;

    int ans = 0;
    for (auto &it : mp)
        ans += (it.second * (it.second - 1) / 2) * 8;
    return ans;
}

int main() {
    int n = 4;
    int arr[] = {2, 4, 6, 3};
    cout << countTuples(arr, n);
    return 0;
}

Kết quả

8

Tổng số bộ tư có tích bằng nhau là 8.