C++で解く！範囲内の最大奇数約数のXORを求めるクエリ処理

N個の整数からなる配列と、範囲を指定するQ個のクエリが与えられます。各クエリに対して、指定された範囲内に含まれる各数値の「最大奇数約数」のXOR（排他的論理和）を返す必要があります。

最大奇数約数とは、ある数Nを割り切る最大の奇数のことです。例えば、6の最大奇数約数は3です。

入力: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } }
出力:
query1: 7
query2: 1

説明: nums配列の各要素の最大奇数約数は { 3, 3, 7, 5 } です。
クエリ1ではインデックス0、1、2のXORである「7」を、クエリ2ではインデックス1、2、3のXORである「1」を求めます。

解法のアプローチ

シンプルなアプローチ

まず単純な方法としては、配列の全要素について最大奇数約数を求めます。その後、クエリで指定された範囲ごとに、範囲内の要素のXORを毎回計算して返します。ただし、この方法はクエリのたびにO(N)の計算が必要となるため、クエリ数が多い場合には非効率です。

効率的なアプローチ

この問題を効率的に解くには、最大奇数約数を格納した配列から事前に「累積XOR配列（プレフィックスXOR配列）」を作成しておきます。こうすることで、範囲内のXORを毎回計算する代わりに、prefix_XOR[R] ^ prefix_XOR[L-1] を計算するだけで答えが得られ、各クエリをO(1)で処理できます。

累積XOR配列とは、各要素が「先頭からその要素までのすべての要素のXOR」を格納する配列のことです。

C++での実装例

#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];
    // 各要素の最大奇数約数を格納する配列を作成
    for (int i = 0; i < n; i++) {
        while (nums[i] % 2 != 1)
            nums[i] /= 2;
        prefix_XOR[i] = nums[i];
    }
    // prefix_XOR配列を累積XOR配列に変換
    for (int i = 1; i < n; i++)
        prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
    // 結果を求めるクエリ配列
    int query[2][2] = {{0, 2},{1, 3}};
    int q = sizeof(query) / sizeof(query[0]);
    // 各クエリの結果を出力
    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[i][1]] ^ prefix_XOR[query[i][0] - 1];
            cout << result << endl;
        }
    }
    return 0;
}

出力結果

7
1

コードの解説

• まずprefix_XOR配列を作成して各要素の最大奇数約数を格納し、その後この配列を累積XOR配列へと変換します。

• 最大奇数約数は、数値を2で割り続け、2で割った剰余が1（奇数）になった時点の値として求められます。

• 累積XOR配列は、配列を走査しながら現在の要素と直前の要素のビットごとのXORを取ることで作成できます。

• クエリの結果は、左端が0の場合は prefix_XOR[R] を、それ以外の場合は prefix_XOR[R] ^ prefix_XOR[L-1] を計算することで求まります。

まとめ

本記事では、配列の指定された範囲内にある各数値の最大奇数約数のXORを求める問題について解説しました。各要素の最大奇数約数を求めた上で、累積XOR配列を活用することで、クエリあたりO(1)という高速な処理が可能になります。この手法は、C言語やJava、Pythonなど他のプログラミング言語でも同様に応用できます。本記事が皆様のお役に立てば幸いです。