C++範圍內最大奇數約數的異或查詢

給定一個包含 N 個整數的陣列和 Q 個範圍查詢。對於每個查詢，我們需要傳回範圍內每個數字的最大奇數除數的異或。

最大奇數除數是可以整除數字 N 的最大奇數，例如 。例如，6 的最大奇數約數是 3。

Input: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } }
Output:
query1: 7
query2: 1

Explanation: greatest odd divisors of nums array are { 3, 3, 7, 5 }.
For query 1 we need to find the XOR of indexes 0, 1, and 2 which is 7, and for query2 we need to find XOR of indexes 1, 2, and 3 which is 1.

求解的方法

簡單方法

首先，在簡單方法中，我們需要找到所有陣列元素的最大奇數約數。然後根據查詢的範圍，我們需要計算範圍內每個元素的異或並傳回。

有效的方法

解決這個問題的一個有效方法是創建包含最大奇數除數的數組的前綴異或數組prefix_XOR[]，而不是每次對範圍內的每個數字進行異或並回傳prefix_XOR[R] - prefix_XOR[L-1]。

Prefix異或陣列是其中每個元素都包含所有先前元素的異或的陣列。

範例

#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];
    // creating an array
    // containing Greatest odd divisor of each element.
    for (int i = 0; i < n; i++) {
        while (nums[i] % 2 != 1)
            nums[i] /= 2;
        prefix_XOR[i] = nums[i];
    }
    // changing prefix_XOR array to prefix xor array.
    for (int i = 1; i < n; i++)
        prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
    // query array to find result of these queries.
    int query[2][2] = {{0, 2},{1, 3}};
    int q = sizeof(query) / sizeof(query[0]);
    // finding results of queries.
    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[0][1]] ^ prefix_XOR[query[i][0] - 1];
            cout <<  result << endl;
        }
    }
    return 0;
}

輸出

7
4

上述程式碼說明

• 建立prefix_XOR陣列來儲存每個元素的最大奇數除數，然後將此數組變更為前綴異或數組。

• 最大奇除數的計算方法是將其除以二，直到模 2 得到 1。

• 建立前綴異或陣列通過遍歷數組並將當前元素與前一個元素進行位元異或。

• 查詢結果是透過減去 prefix_XOR[] 陣列的右索引來計算的(left - 1) prefix_XOR[] 陣列的索引。

結論

在本教程中，我們討論了一個需要查找 XOR 的問題給定數組範圍內每個數字的最大奇數除數。我們討論了一種解決此問題的方法，即找到每個元素的最大奇數除數並使用前綴異或數組。我們也討論了針對此問題的 C 程序，我們可以使用 C、Java、Python 等程式語言來完成此問題。我們希望本文對您有所幫助。

以上是C++範圍內最大奇數約數的異或查詢的詳細內容。更多資訊請關注PHP中文網其他相關文章！