My Solutions
1. Use the binary search\n\n/**\n * Time Complexity: O(n * log(bound) * log(bound))\n * Space Complexity: O(1)\n * where `n` is the length of the vector `querie
**1. Use the binary search**\n```\n/**\n * Time Complexity: O(n * log(bound) * log(bound))\n * Space Complexity: O(1)\n * where `n` is the length of the vector `queries`\n *       `bound` is the maximum value of the `from`s and the `to`s of all queries `queries`\n */\nclass Solution {\n public:\n  vector<int> findProductsOfElements(const vector<vector<long long>> &queries) {\n    constexpr int lower_i = 0;\n    constexpr int upper_i = 1;\n    constexpr int mod_i = 2;\n    const int n = static_cast<int>(queries.size());\n    vector<int> ret(n);\n    for (int i = 0; i < n; ++i) {\n      const long long lower = queries[i][lower_i] + 1;\n      const long long upper = queries[i][upper_i] + 1;\n      const int mod = static_cast<int>(queries[i][mod_i]);\n      \n      const auto [lower_num, lower_bit] = get_stats(lower);\n      const auto [upper_num, upper_bit] = get_stats(upper);\n      if (lower_num == upper_num) {\n        ret[i] = multiply_bits(lower_num, lower_bit, upper_bit, mod);\n      } else {\n        ret[i] = multiply_bits(lower_num, lower_bit, numeric_limits<int>::max(), mod);\n        for (int bit = 0; (upper_num >> bit) > 0; ++bit) {\n          ret[i] = static_cast<int>(static_cast<long long>(ret[i]) * power(1LL << bit, count_bit(bit, upper_num - 1) - count_bit(bit, lower_num), mod) % mod);\n        }\n        ret[i] = static_cast<int>(static_cast<long long>(ret[i]) * multiply_bits(upper_num, 1, upper_bit, mod) % mod);\n      }\n    }\n    return ret;\n  }\n  \n private:\n  long long count_bit(const int bit, const long long upper) {\n    const long long half = 1LL << bit;\n    const long long whole = half << 1;\n    return (upper / whole) * half + max(0LL, upper % whole - (half - 1));\n  }\n  \n  long long count_bits(const long long upper) {\n    long long ret = 0;\n    for (int bit = 0; (upper >> bit) > 0; ++bit) {\n      ret += count_bit(bit, upper);\n    }\n    return ret;\n  }\n  \n  pair<long long, int> get_stats(const long long length) {\n    long long low = 1;\n    long long high = length;\n    while (low < high) {\n      const long long mid = low + ((high - low) >> 1);\n      if (count_bits(mid) < length) {\n        low = mid + 1;\n      } else {\n        high = mid;\n      }\n    }\n    return make_pair(high, length - count_bits(high - 1));\n  }\n  \n  int multiply_bits(const long long number, const int lower_bit, const int upper_bit, const int mod) {\n    int ret = 1;\n    for (long long bit_value, bit = 1, num = number; num > 0; num -= bit_value, ++bit) {\n      bit_value = num & -num;\n      if (bit >= lower_bit && bit <= upper_bit) {\n        ret = static_cast<int>(ret * bit_value % mod);\n      }\n    }\n    return ret;\n  }\n  \n  int power(const long long number, const long long pow, const int mod) {\n    int ret = 1;\n    int base = static_cast<int>(number % mod);\n    for (long long p = pow; p > 0; p >>= 1) {\n      if ((p & 0b1) == 0b1) {\n        ret = static_cast<int>((static_cast<long long>(ret) * base) % mod);\n      }\n      base = static_cast<int>(static_cast<long long>(base) * base % mod);\n    }\n    return ret;\n  }\n};\n```\n**2. Try every bit**\n```\n/**\n * let `p(number)` = [`p1`, `p2`, `p3`, ...] such that `number` = (2 ^ `p1`) + (2 ^ `p2`) + (2 ^ `p3`) + ...\n * p(0) = []\n * p(1) = [0]\n * p(2) = [1]\n * p(3) = [0, 1]\n * p(4) = [2]\n * p(5) = [0, 2]\n * p(6) = [1, 2]\n * p(7) = [0, 1, 2]\n * p(8) = [3]\n * p(9) = [0, 3]\n * p(10) = [1, 3]\n * ...\n *\n * let count(i) = len(p(0)) + len(p(1)) + ... + len(p((2 ^ i) - 1))\n * count(0) = len(p(0)) = 0\n * count(1) = len(p(0)) + len(p(1)) = 1\n * count(2) = len(p(0)) + len(p(1)) + len(p(2)) + len(p(3)) = 4\n * ...\n * count(n) = 2 * count(n - 1) + 2 ^ (n - 1)\n * count(n) = n * (2 ^ (n - 1))\n *\n * let p_sum(i) = sum(p(0)) + sum(p(1)) + ... + sum(p((2 ^ i) - 1))\n * let p_sum(0) = 0\n * p_sum(1) = sum(p(0)) + sum(p(1)) = 0\n * p_sum(2) = sum(p(0)) + sum(p(1)) + sum(p(2)) + sum(p(3)) = 2\n * ...\n * p_sum(n) = 2 * p_sum(n - 1) + (2 ^ (n - 1)) * (n - 1)\n * p_sum(n) = n * (n - 1) * (2 ^ (n - 2))\n *\n * Time Complexity: O(n * log(bound))\n * Space Complexity: O(1)\n * where `n` is the length of the vector `queries`\n *       `bound` is the maximum value of the `from`s and the `to`s of all queries `queries`\n */\nclass Solution {\n public:\n  vector<int> findProductsOfElements(const vector<vector<long long>> &queries) {\n    constexpr int from_i = 0;\n    constexpr int to_i = 1;\n    constexpr int mod_i = 2;\n    const int n = static_cast<int>(queries.size());\n    vector<int> ret(n);\n    for (int i = 0; i < n; ++i) {\n      const long long from = queries[i][from_i];\n      const long long to = queries[i][to_i] + 1;\n      const int mod = static_cast<int>(queries[i][mod_i]);\n      ret[i] = power(get_power_sum(to) - get_power_sum(from), mod);\n    }\n    return ret;\n  }\n  \n private:\n  long long get_power_sum(const long long q) {\n    const int most_bit = get_most_bit(q);\n    long long n = 0LL;\n    long long remains = q;\n    long long ret = 0LL;\n    for (int count_one = 0, sum_p = 0, bit = most_bit; remains > 0 && bit > -1; --bit) {\n      const long long count = count_one * (1LL << bit) + (bit > 0 ? static_cast<long long>(bit) << (bit - 1) : 0);\n      if (count > remains) {\n        continue;\n      }\n      n |= 1LL << bit;\n      remains -= count;\n      ret += sum_p * (1LL << bit) + (bit > 1 ? ((static_cast<long long>(bit) * (bit - 1)) << (bit - 2)) : 0);\n      ++count_one;\n      sum_p += bit;\n    }\n    \n    for (int bit = 0; bit < most_bit + 1 && remains > 0; ++bit) {\n      if (((n >> bit) & 0b1) == 0b1) {\n        ret += bit;\n        --remains;\n      }\n    }\n    return ret;\n  }\n  \n  int get_most_bit(const long long q) {\n    int ret = 0;\n    for (long long num = q; num > 0; num >>= 1) {\n      ++ret;\n    }\n    return ret - 1;\n  }\n  \n  int power(const long long pow, const int mod) {\n    int ret = 1;\n    int base = 2;\n    for (long long p = pow; p > 0; p >>= 1) {\n      if ((p & 0b1) == 0b1) {\n        ret = static_cast<int>(static_cast<long long>(ret) * base % mod);\n      }\n      base = static_cast<int>(static_cast<long long>(base) * base % mod);\n    }\n    return ret % mod;\n  }\n};\n```
[]