3145. 大数组元素的乘积

3145. 大数组元素的乘积

题目链接：3145. 大数组元素的乘积

代码如下：

//参考链接:https://leetcode.cn/problems/find-products-of-elements-of-big-array/solutions/2774549/olog-shi-tian-fa-pythonjavacgo-by-endles-w2l4
class Solution 
{
public:vector<int> findProductsOfElements(vector<vector<long long>>& queries) {vector<int> res;for(auto& query:queries){auto er=sum_e(query[1]+1);auto el=sum_e(query[0]);res.push_back(pow(2,er-el,query[2]));}return res;}private:int pow(long long x,long long n,long long mod){long long res=1%mod;for(;n;n/=2){if(n%2){res=res*x%mod;}x=x*x%mod;}return res;}long long sum_e(long long k){long long res=0,n=0,count1=0,sum_i=0;for(long long i=__lg(k+1);i;i--){long long c=(count1<<i)+(i<<(i-1));// 新增的幂次个数if(c<=k){k-=c;res+=(sum_i<<i)+((i*(i-1)/2)<<(i-1));sum_i+=i;// 之前填的 1 的幂次之和count1++;// 之前填的 1 的个数n|=1LL<<i;// 填 1}}//最低位单独计算if(count1<=k){k-=count1;res+=sum_i;n|=1;// 最低位填 1}//剩余的 k 个幂次，由 n 的低 k 个 1 补充while(k--){res+=__builtin_ctzll(n);n&=n-1;// 去掉最低位的 1（置为 0）}return res;}
};