Binary Search + Count contribution of each bit till given index
Intuition\nWe\'ll count frequency of each bit till index i\n\n# Approach\nmaintain two vectors vector<int> cnt1(60,0), cnt2(60, 0) where cnt1[i] = freq of ith b
# Intuition\nWe\'ll count frequency of each bit till index i\n\n# Approach\nmaintain two vectors `vector<int> cnt1(60,0), cnt2(60, 0)` where `cnt1[i] = freq of ith bit till queries[x][1] index` and  `cnt2[i] = freq of ith bit till queries[x][0]-1` index\n\nThen doing `cnt1[i] - cnt2[i]` for every ith bit will tell us how many times `ith` bit appears in index range `[queries[x][0], queries[x][1]]`.\n\nSince, we know the freq of each bit in given range, just do `mod_pow(1<<i, freq[i], mod)` to find contribution of `ith` bit in final ans.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nT.C = `O(len(queries) * log(MX) * LIM)`, where `MX = 1e15` and `LIM = 60`\n\n# Code\n```\nusing ll = long long;\nconst ll MX = 1e15 + 6, LIM = 60;\nclass Solution {\npublic:\n    \n    ll add(ll x, ll y, ll mod) { ll res = 0ll + x + y; return (res >= mod ? res - mod : res); }\n    ll sub(ll x, ll y, ll mod) { ll res = x - y; return (res < 0 ? res + mod : res); }\n    ll mul(ll x, ll y, ll mod) { x %= mod, y %= mod; ll res = 1ll * x * y; return (res >= mod ? res % mod : res); }\n    ll mod_pow(ll x, ll y, ll mod) { if (y <= 0) return 1; ll ans = 1; x %= mod; while (y) { if (y & 1) ans = mul(ans, x, mod); x = mul(x, x, mod); y >>= 1; } return ans; }\n    ll mod_inverse(ll x, ll mod) {return mod_pow(x, mod - 2, mod);}\n    \n    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {\n        int m = queries.size();\n        vector<int> ret;\n        \n        // find the integer x such that integers [1,2,3 .... x]\'s\n        // powers of 2 makes up till any index i\n        // [1,2 ... x-1]\'s power of 2 representation and some or all \n        // power of 2 of x\'s total count equals index i\n        auto calc = [&] (ll n)\n        {\n            if (n <= 0) return n;\n            ll lo = 1, hi = MX;\n            while (lo <= hi)\n            {\n                ll mid = (lo+hi)/2, sum = 0;\n                for (int i=0; i<LIM; i++)\n                {\n                    ll p = (1ll<<(i+1));\n                    ll cur = ((mid+1)/p) * (1ll<<i);\n                    cur += max(0ll, ((mid+1)%p) - (1ll<<i));\n                    sum += cur;\n                }\n                if (sum >= n) hi = mid-1;\n                else lo = mid+1;\n            }\n            return hi+1;\n        };\n        \n        // finds freq of each bit till index tot-1\n        auto calc2 = [&] (ll n, ll tot)\n        {\n            vector<ll> cnt(LIM, 0);\n            if (n <= 0)  return cnt;\n            ll sum = 0;\n            for (int i=0; i<LIM; i++)\n            {\n                ll p = (1ll<<(i+1));\n                ll cur = (n/p) * (1ll<<i);\n                cur += max(0ll, (n%p) - (1ll<<i));\n                sum += cur;\n                cnt[i] = cur;\n            }\n            if (sum < tot)\n            {\n                for (int i=0; i<LIM; i++)\n                {\n                    if (sum >= tot) break;\n                    if ((n>>i)&1)\n                    {\n                        cnt[i]++;\n                        sum++;\n                    }\n                }\n            }\n            return cnt;\n        };\n        \n        for (auto q:queries)\n        {\n            vector<ll> v1 = calc2(calc(q[1]+1), q[1]+1), v2 = calc2(calc(q[0]), q[0]);\n   \n            ll val = 1;\n            for (int i=0; i<LIM; i++)\n            {\n                ll p = (1ll<<i);\n                ll temp = mod_pow(p, v1[i]-v2[i], q[2]);\n                val = (val*temp) % q[2];\n            }\n            ret.push_back((int)val);\n        }\n        return ret;\n    }\n};\n```
['Binary Search', 'Bit Manipulation', 'C++']