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中文网其他相关文章！