Đếm cặp từ hai mảng cho kết quả modulo bằng K trong C++

Cho hai mảng số dương và giá trị K. Tìm số cặp duy nhất (A,B) với A từ mảng 1, B từ mảng 2 sao cho A%B=K hoặc B%A=K.

Ví dụ

Đầu vào − arr_1[] = {1,2,5,3,4}, arr_2[] = {7,1,3}, k=2

Đầu ra − 2

Giải thích − (5,7): 7%5=2, (5,3): 5%3=2.

Đầu vào − arr_1[] = {2,5}, arr_2[] = {3,7}, k=1

Đầu ra − 2

Giải thích − (2,3): 3%2=1, (2,7): 7%2=1.

Phương pháp giải

Duyệt 2 vòng lặp qua hai mảng. Với mỗi cặp (arr_1[i], arr_2[j]), kiểm tra điều kiện modulo. Dùng set> để lưu cặp duy nhất. Kết quả = size của set.

• Hàm modulo_pairs(int arr_1[], int arr_2[], int size1, int size2, int k).
• set> se.
• Lặp i=0..size1-1, j=0..size2-1:
  • Nếu arr_1[i] > arr_2[j] và arr_1[i] % arr_2[j] == k → insert.
  • Ngược lại nếu arr_2[j] % arr_1[i] == k → insert.
• Trả về se.size().

Ví dụ code

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

int modulo_pairs(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int k) {
    int count = 0;
    set<pair<int, int>> se;
    for (int i = 0; i < size_arr_1; i++) {
        for (int j = 0; j < size_arr_2; j++) {
            if (arr_1[i] > arr_2[j]) {
                if (arr_1[i] % arr_2[j] == k) se.insert({arr_1[i], arr_2[j]});
            } else {
                if (arr_2[j] % arr_1[i] == k) se.insert({arr_2[j], arr_1[i]});
            }
        }
    }
    count = se.size();
    return count;
}

int main() {
    int arr_1[] = {2, 7, 1, 9};
    int arr_2[] = {4, 10, 3, 10};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int k = 3;
    cout << "Count of pairs from two arrays whose modulo operation yields K are: " << modulo_pairs(arr_1, arr_2, size_arr_1, size_arr_2, k);
    return 0;
}

Đầu ra

Count of pairs from two arrays whose modulo operation yields K are: 2