# 范圍最大奇數的 XOR 查詢 > 原文： [https://www.geeksforgeeks.org/queries-xor-greatest-odd-divisor-range/](https://www.geeksforgeeks.org/queries-xor-greatest-odd-divisor-range/) 給定 **N** 個正整數的數組。 有**個 Q** 查詢，每個查詢都包含一個范圍[L，R]。 對于每個查詢輸出，該范圍內每個數字的最大奇數除數的異或。 **示例**： ``` Input : arr[] = { 3, 4, 5 } query 1: [0, 2] query 2: [1, 2] Output : 7 4 Greatest odd divisor are: { 3, 1, 5 } XOR of 3, 1, 5 is 7 XOR of 1, 5 is 4 Input : arr[] = { 2, 1, 2 } query 1: [0, 2] Output : 1 ``` 這個想法是預先計算數組的最大奇數除數，并將其存儲在數組中，例如 preXOR []。 現在，預先計算并存儲數組 preXOR []的前綴 XOR。 要回答每個查詢，請返回（preXOR [r] xor preXOR [l-1]）。 以下是此方法的實現： ## C++ ```cpp #include <bits/stdc++.h> using namespace std; // Precompute the prefix XOR of greatest? // odd divisor void prefixXOR(int arr[], int preXOR[], int n) { ????// Finding the Greatest Odd divisor ????for (int i = 0; i < n; i++) { ????????while (arr[i] % 2 != 1) ????????????arr[i] /= 2; ????????preXOR[i] = arr[i]; ????} ????// Finding prefix XOR ????for (int i = 1; i < n; i++) ????????preXOR[i] = preXOR[i - 1] ^ preXOR[i]; } // Return XOR of the range int query(int preXOR[], int l, int r) { ????if (l == 0) ????????return preXOR[r]; ????else ????????return preXOR[r] ^ preXOR[l - 1]; } // Driven Program int main() { ????int arr[] = { 3, 4, 5 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int preXOR[n]; ????prefixXOR(arr, preXOR, n); ????cout << query(preXOR, 0, 2) << endl; ????cout << query(preXOR, 1, 2) << endl; ????return 0; } ```