C++ Bit count and binary search, Clean code with a lot explanitions.
Intuition\n\nLet\'s think top-down and conquer each individual tasks one by one.\n\n Describe your first thoughts on how to solve this problem. \n1. The big_num
# Intuition\n\nLet\'s think top-down and conquer each individual tasks one by one.\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. The `big_nums` array is all power of 2. So we can represent it with the power only.\n   ```\n   [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, 1, 8, ...]  (2 ^ bit)\n    -  -  ----  -  ----  ----  -------  -  ----\n   [0, 1, 0, 1, 2, 0, 2, 1, 2, 0, 1, 2, 3, 0, 3, ...]  (bit)\n    -  -  ----  -  ----  ----  -------  -  ----\n2. Once converted, the **multiplication** will become **addition**. We will then need to sum the value from `from = query[0]` to `to = query[1]`.\n   `2^i * 2^j = 2^(i + j)`\n3. The above summation can also be converted as prefix sum, so that we can easily get `prefix_sum[to] - prefix_sum[from - 1]`.\n4. Assuming we have a function `LL prefixSumTillIndex(index)` which can sum the value of each bit for the first `index` elements in the converted `big_nums` (took `log_2` of it).\n   Then we can simplly calculate the result with some `mod` helper function:\n    ```C++\n    for (const auto& query : queries) {\n        LL prefix_sum_1 = prefixSumTillIndex(query[0]);\n        LL prefix_sum_2 = prefixSumTillIndex(query[1] + 1);\n            \n        // This is `2^sum % mod`\n        result.push_back(pow(2, prefix_sum_2 - prefix_sum_1, query[2]));\n        } \n    ```\n   Where the helper `pow` function calculates `(x ^ y % mod)`:\n    ```C++\n    // Calculate `(x ^ y) % mod` by converting the y into binary bits.\n    int pow(LL x, LL y, int mod) {\n        if (y <= 0) {\n            return 1 % mod;\n        }\n        x %= mod;\n        LL result = 1;\n        while (y) {\n            if (y & 1) {\n                result = multiply(result, x, mod);\n            }\n            x = multiply(x, x, mod);\n            y >>= 1;\n        }\n        return result;\n    }\n\n    int multiply(LL x, LL y, int mod) {\n        return ((x % mod) * (y % mod)) % mod;\n    }\n    ```\n5. However now the problem is **how to implement function `prefixSumTillIndex`**, it seems simpler to sum bits from 1 to a **`value`**, instead of all bits which is **`index`** because it\'a hard to control how many bits 1 (indexes occupied) per value. So we will need another helper function to find the value for a given index: `LL getValueFromIndex(LL index)`. But let\'s implement prefixSum first assuming that function is already done:\n    ```C++\n    LL prefixSumTillIndex(LL index) {\n        LL value = getValueFromIndex(index);\n        auto [bit_sum, bit_count] = sumAndCountBitsBeforeValue(value);\n        // Also include the last value\'s partial bits.\n        if (bit_count < index) {\n            for (int bit = 0; bit_count < index; bit++, value >>= 1) {\n                bit_sum += bit * (value % 2);\n                bit_count += value % 2;\n            }\n        }\n        return bit_sum;\n    }\n\n    // Count the bits for all numbers from 1 to `value - 1`.\n    // Return the bit value sum and total count.\n    pair<LL, LL> sumAndCountBitsBeforeValue(LL value) {\n        LL bit_sum = 0;\n        LL bit_count = 0;\n        for (LL bit = 0, power = 1; power < value; bit++, power <<= 1) {\n            LL cur = (value >> (bit + 1)) << bit;\n            cur += max(0LL, (value % (power << 1)) - power);\n            bit_count += cur;\n            bit_sum += bit * cur;\n        }\n        return {bit_sum, bit_count};\n    }\n    ```\n6. Now for `LL getValueFromIndex(LL index)`, this would lead me to think about binary serach, by reusing the function `sumAndCountBitsBeforeValue` above:\n    ```C++\n    LL getValueFromIndex(LL index) {\n        index++;\n        LL low = 1, high = 1LL << 50;\n\n        while (low < high) {\n            LL mid = low + (high - low) / 2;\n            if (sumAndCountBitsBeforeValue(mid + 1).second < index) {\n                low = mid + 1;\n            } else {\n                high = mid;\n            }\n        }\n        return low;\n    }\n    ```\n7. Finally we get every component ready, the finally solution is as follows.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++\nusing LL = long long;\n\nclass Solution {\npublic:\n    vector<int> findProductsOfElements(vector<vector<LL>>& queries) {\n        vector<int> result;\n        result.reserve(queries.size());\n        for (const auto& query : queries) {\n            LL prefix_sum_1 = prefixSumTillIndex(query[0]);\n            LL prefix_sum_2 = prefixSumTillIndex(query[1] + 1);\n\n            result.push_back(pow(2, prefix_sum_2 - prefix_sum_1, query[2]));\n        }\n\n        return result;\n    }\n\nprivate:\n    // Count the bits for all numbers from 1 to `value - 1`.\n    // Return the bit value sum and total count.\n    pair<LL, LL> sumAndCountBitsBeforeValue(LL value) {\n        LL bit_sum = 0;\n        LL bit_count = 0;\n        for (LL bit = 0, power = 1; power < value; bit++, power <<= 1) {\n            LL cur = (value >> (bit + 1)) << bit;\n            cur += max(0LL, (value % (power << 1)) - power);\n            bit_count += cur;\n            bit_sum += bit * cur;\n        }\n        return {bit_sum, bit_count};\n    }\n\n    LL getValueFromIndex(LL index) {\n        index++;\n        LL low = 1, high = 1LL << 50;\n\n        while (low < high) {\n            LL mid = low + (high - low) / 2;\n            if (sumAndCountBitsBeforeValue(mid + 1).second < index) {\n                low = mid + 1;\n            } else {\n                high = mid;\n            }\n        }\n        return low;\n    }\n\n    LL prefixSumTillIndex(LL index) {\n        LL value = getValueFromIndex(index);\n        auto [bit_sum, bit_count] = sumAndCountBitsBeforeValue(value);\n        // Also include the last value\'s partial bits.\n        if (bit_count < index) {\n            for (int bit = 0; bit_count < index; bit++, value >>= 1) {\n                bit_sum += bit * (value % 2);\n                bit_count += value % 2;\n            }\n        }\n        return bit_sum;\n    }\n\n    // Calculate `(x ^ y) % mod` by converting the y into binary bits.\n    int pow(LL x, LL y, int mod) {\n        if (y <= 0) {\n            return 1 % mod;\n        }\n        x %= mod;\n        LL result = 1;\n        while (y) {\n            if (y & 1) {\n                result = multiply(result, x, mod);\n            }\n            x = multiply(x, x, mod);\n            y >>= 1;\n        }\n        return result;\n    }\n\n    int multiply(LL x, LL y, int mod) {\n        return ((x % mod) * (y % mod)) % mod;\n    }\n};\n```
['Binary Search', 'Bit Manipulation', 'C++']