C++ Truy vấn XOR của ước số lẻ lớn nhất trong khoảng

Cho một mảng N số nguyên và Q truy vấn về các khoảng. Với mỗi truy vấn, ta cần trả về XOR của ước số lẻ lớn nhất của từng số trong khoảng đó.

Ước số lẻ lớn nhất là số lẻ lớn nhất có thể chia hết cho số N. Ví dụ: ước số lẻ lớn nhất của 6 là 3.

Input: nums[] = { 3, 6, 7, 10 }, query[] = { { 0, 2 }, { 1, 3 } }
Output: truy vấn 1: 7, truy vấn 2: 1
Giải thích: ước số lẻ lớn nhất của mảng nums là { 3, 3, 7, 5 }. Với truy vấn 1, ta cần tìm XOR của chỉ số 0, 1, 2 là 7, và truy vấn 2 tìm XOR của chỉ số 1, 2, 3 là 1.

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

Phương pháp đơn giản

Đầu tiên, ta tìm ước số lẻ lớn nhất của tất cả các phần tử mảng. Sau đó, theo khoảng của truy vấn, ta tính XOR của từng phần tử trong khoảng và trả về kết quả.

Phương pháp hiệu quả

Cách hiệu quả hơn là tạo mảng tiền tố XOR prefix_XOR[] chứa các ước số lẻ lớn nhất thay vì tính XOR mỗi lần. Kết quả truy vấn [L, R] sẽ là prefix_XOR[R] ^ prefix_XOR[L-1] (nếu L > 0) hoặc prefix_XOR[R] (nếu L = 0).

Mảng tiền tố XOR là mảng mà mỗi phần tử chứa XOR của tất cả các phần tử trước đó.

Ví dụ minh họa

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

int main() {
    int nums[] = { 3, 6, 7, 10 };
    int n = sizeof(nums) / sizeof(nums[0]);
    int prefix_XOR[n];

    // Tạo mảng chứa ước số lẻ lớn nhất của từng phần tử
    for (int i = 0; i < n; i++) {
        while (nums[i] % 2 != 1)
            nums[i] /= 2;
        prefix_XOR[i] = nums[i];
    }

    // Chuyển đổi thành mảng tiền tố XOR
    for (int i = 1; i < n; i++)
        prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];

    // Mảng truy vấn
    int query[2][2] = {{0, 2}, {1, 3}};
    int q = sizeof(query) / sizeof(query[0]);

    // Xử lý các truy vấn
    for (int i = 0; i < q; i++) {
        if (query[i][0] == 0)
            cout << prefix_XOR[query[i][1]] << endl;
        else {
            int result = prefix_XOR[query[i][1]] ^ prefix_XOR[query[i][0] - 1];
            cout << result << endl;
        }
    }
    return 0;
}

Kết quả

7 1

Giải thích mã nguồn

• Mảng prefix_XOR được tạo để lưu ước số lẻ lớn nhất, sau đó chuyển thành mảng tiền tố XOR.
• Ước số lẻ lớn nhất được tính bằng cách chia liên tục cho 2 cho đến khi chia dư 1.
• Mảng tiền tố XOR được xây dựng bằng cách duyệt mảng và thực hiện XOR bitwise giữa phần tử hiện tại và phần tử trước.
• Kết quả truy vấn được tính bằng phép XOR giữa prefix_XOR[R] và prefix_XOR[L-1].

Kết luận

Trong bài viết này, ta đã thảo luận về bài toán tìm XOR của ước số lẻ lớn nhất trong khoảng cho trước. Ta đã trình bày phương pháp sử dụng mảng tiền tố XOR sau khi tính ước số lẻ lớn nhất. Chương trình C++ minh họa có thể triển khai tương tự bằng C, Java, Python, v.v. Hy vọng bài viết hữu ích cho bạn.