Đếm cặp trong mảng thỏa LCM(arr[i], arr[j]) > min(arr[i], arr[j]) trong C++

Cho mảng số nguyên dương. Đếm cặp (arr[i], arr[j]) sao cho LCM(arr[i], arr[j]) > min(arr[i], arr[j]). Lưu ý: cặp (i,j) và (j,i) chỉ đếm một lần.

Ví dụ

Đầu vào − arr[] = [1,5,4,2]

Đầu ra − 6

Giải thích − 6 cặp: (1,5) LCM=5>1, (1,4) LCM=4>1, (1,2) LCM=2>1, (5,4) LCM=20>4, (5,2) LCM=10>2, (4,2) LCM=4>2.

Đầu vào − arr[] = [3,3,6]

Đầu ra − 2

Giải thích − (3,6) LCM=6>3 (2 cặp do có 2 số 3).

Phương pháp giải

Điều kiện chỉ sai khi arr[i] == arr[j] (LCM = chính nó = min). Do đó, kết quả = tổng cặp có thể tạo - cặp hai phần tử bằng nhau.

• Tổng cặp = n*(n-1)/2.
• Dùng unordered_map đếm tần suất. Với tần suất f, cặp trùng = f*(f-1)/2.
• Kết quả = tổng - tổng cặp trùng.

Ví dụ code

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

int conditional_pair(int arr[], int size) {
    int count = 0;
    unordered_map<int, int> um;
    for (int i = 0; i < size; i++) um[arr[i]]++;
    for (auto it : um) {
        int f = it.second;
        count += f * (f - 1) / 2;
    }
    int total = size * (size - 1) / 2;
    count = total - count;
    return count;
}

int main() {
    int arr[] = {4, 1, 7, 3, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are: " << conditional_pair(arr, size);
    return 0;
}

Đầu ra

Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are: 10