C++에서 범위 내 최대 홀수 제수에 대한 XOR 쿼리

N개의 정수와 Q 범위 쿼리가 포함된 배열이 제공됩니다. 각 쿼리에 대해 범위에 있는 각 숫자의 가장 큰 홀수 제수에 대한 XOR을 반환해야 합니다.

가장 큰 홀수 약수는 와 같이 숫자 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.

해결 방법

간단한 방법

먼저 간단한 방법에서는 모든 배열 요소의 가장 큰 홀수 약수를 찾아야 합니다. 그런 다음 쿼리 범위를 기반으로 범위에 있는 각 요소의 XOR을 계산하여 반환해야 합니다.

효율적인 접근 방식

이 문제를 해결하는 효율적인 방법은 매번 범위의 각 숫자를 XOR하고 prefix_XOR[R ] - prefix_XOR을 반환하는 대신 가장 큰 홀수 약수가 있는 배열을 포함하는 접두사 XOR 배열 prefix_XOR[]을 만드는 것입니다. [엘-1].

Prefix XOR 배열은 각 요소가 모든 이전 요소의 XOR을 포함하는 배열입니다.

Example

#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;
}

Output

7
4

위의 코드 설명

• prefix_XOR 배열을 생성하여 각 요소의 가장 큰 홀수 제수를 저장한 다음 이 배열을 접두사 XOR 배열로 변경합니다.

• 가장 큰 홀수 제수는 모듈로 2가 1이 될 때까지 2로 나누어 계산됩니다.

• 배열을 반복하고 현재 요소와 이전 요소의 비트 XOR을 수행하여 접두사 XOR 배열을 만듭니다.

• prefix_XOR[] 배열의 오른쪽 인덱스를 빼서 쿼리 결과를 계산합니다. (왼쪽 - 1) prefix_XOR[] 배열의 인덱스입니다.

결론

이 튜토리얼에서는 XOR을 사용하여 주어진 배열 범위에서 각 숫자에 대해 가장 큰 홀수 제수를 찾아야 하는 문제에 대해 논의했습니다. 우리는 각 요소에 대해 가장 큰 홀수 약수를 찾고 접두사 XOR 배열을 사용하여 이 문제를 해결하는 방법을 논의했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램에 대해 논의했으며 C, Java, Python 등과 같은 프로그래밍 언어를 사용하여 이를 수행할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++에서 범위 내 최대 홀수 제수에 대한 XOR 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!