# 在給定范圍內對偶數或奇數概率的查詢 > 原文： [https://www.geeksforgeeks.org/queries-probability-even-odd-number-given-ranges/](https://www.geeksforgeeks.org/queries-probability-even-odd-number-given-ranges/) 給定大小為 **N** 的數組 **A** ，其中包含整數。 我們必須回答 **Q** 個查詢，其中每個查詢的形式為： * **K L R**：如果 K = 0，則必須找到從數組 A 的段[L，R]（均包括）中選擇**甚至**編號的可能性。 * **K L R**：如果 K = 1，則必須找到從數組 A 的線段[L，R]（包括兩端）中選擇**奇數**數字的可能性。 對于每個查詢，打印兩個整數 **p** 和 **q** ，它們表示概率 p / q。 p 和 q 都簡化為最小形式。 如果 p 為 0，則打印 0；或者如果 p 等于 q，則打印 1；否則，僅打印 p 和 q。 **示例**： ``` Input : N = 5, arr[] = { 6, 5, 2, 1, 7 } query 1: 0 2 2 query 2: 1 2 5 query 3: 0 1 4 Output : 0 3 4 1 2 Explanation : First query is to find probability of even element in range [2, 2]. Since range contains a single element 5 which is odd, the answer is 0\. Second query is to find probability of odd element in range [2, 5]. There are 3 odd elements in range probability is 3/4. Third query is for even elements in range from 1 to 4\. Since there are equal even and odd elements, probability is 2/4 which is 1/2. ``` 這個想法是要維護兩個數組，即 even []和 odd []，以保持偶數或奇數元素的數目直到索引 i。 現在，為了回答每個查詢，我們可以通過查找給定查詢范圍內的元素數來計算結果分母 q。 為了找到結果分子，我們從直到 r 的元素中刪除了直到 l – 1 的元素數。 要以最小形式輸出答案，我們找到 p 和 q 的 GCD 并輸出 p / gcd 和 q / gcd。 對于答案 0 和 1，我們將明確指定條件。 以下是此方法的實現： ## C++ ```cpp // CPP program to find probability of even // or odd elements in a given range. #include <bits/stdc++.h> using namespace std; // Number of tuples in a query #define C 3 // Solve each query of K L R form void solveQuery(int arr[], int n, int Q,? ???????????????????????????int query[][C]) { ????// To count number of odd and even? ????// number upto i-th index. ????int even[n + 1]; ????int odd[n + 1]; ????even[0] = odd[0] = 0; ????// Counting number of odd and even? ????// integer upto index i ????for (int i = 0; i < n; i++) { ????????// If number is odd, increment the? ????????// count of odd frequency leave ????????// even frequency same. ????????if (arr[i] & 1) { ????????????odd[i + 1] = odd[i] + 1; ????????????even[i + 1] = even[i]; ????????} ????????// If number is even, increment the ????????// count of even frequency leave odd ????????// frequency same. ????????else { ????????????even[i + 1] = even[i] + 1; ????????????odd[i + 1] = odd[i]; ????????} ????} ????// To solve each query ????for (int i = 0; i < Q; i++) { ????????int r = query[i][2]; ????????int l = query[i][1]; ????????int k = query[i][0]; ????????// Counting total number of element in? ????????// current query ????????int q = r - l + 1; ????????int p; ????????// Counting number of odd or even element? ????????// in current query range ????????if (k) ????????????p = odd[r] - odd[l - 1]; ????????else ????????????p = even[r] - even[l - 1]; ????????// If frequency is 0, output 0 ????????if (!p) ????????????cout << "0" << endl; ????????// If frequency is equal to number of?? ????????// element in current range output 1\. ????????else if (p == q) ????????????cout << "1" << endl; ????????// Else find the GCD of both. If yes,? ????????// output by dividing both number by gcd ????????// to output the answer in reduced form. ????????else { ????????????int g = __gcd(p, q); ????????????cout << p / g << " " << q / g << endl; ????????} ????} } // Driven Program int main() { ????int arr[] = { 6, 5, 2, 1, 7 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int Q = 2; ????int query[Q][C] = { ????????{ 0, 2, 2 }, ????????{ 1, 2, 5 } ????}; ????solveQuery(arr, n, Q, query); ????return 0; } ```