Kiểm tra cặp có tích bằng K trong ma trận C++

Cho ma trận N×M và số K. Kiểm tra tồn tại cặp phần tử trong ma trận có tích = K.

Ví dụ ma trận 4×4 (1..16), K=42 → cặp (6, 7) tồn tại.

Giải thuật (Hashing)

1. Tạo unordered_set
2. Duyệt ma trận: nếu K % matrix[i][j] == 0 và K/matrix[i][j] có trong set → trả về true
3. Thêm matrix[i][j] vào set
4. Duyệt hết không thấy → false

Ví dụ minh họa

#include <iostream>
#include <unordered_set>
#define N 4
#define M 4
using namespace std;

bool isPairPresent(int matrix[N][M], int K) {
    unordered_set<int> s;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if ((K % matrix[i][j] == 0) && (s.find(K / matrix[i][j]) != s.end()))
                return true;
            s.insert(matrix[i][j]);
        }
    }
    return false;
}

int main() {
    int matrix[N][M] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
    int k = 42;
    if (isPairPresent(matrix, k))
        cout << "Cap ton tai";
    else
        cout << "KHONG CO CAP";
}

Kết quả

Cap ton tai