题目描述
一个非负整数 x
的 强数组 指的是满足元素为 2 的幂且元素总和为 x
的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明,x
对应的强数组是独一无二的。
数字 | 二进制表示 | 强数组 |
---|---|---|
1 | 00001 | [1] |
8 | 01000 | [8] |
10 | 01010 | [2, 8] |
13 | 01101 | [1, 4, 8] |
23 | 10111 | [1, 2, 4, 16] |
我们将每一个升序的正整数 i
(即1,2,3等等)的 强数组 连接得到数组 big_nums
,big_nums
开始部分为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...]
。
给你一个二维整数数组 queries
,其中 queries[i] = [fromi, toi, modi]
,你需要计算 (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi
。
请你返回一个整数数组 answer
,其中 answer[i]
是第 i
个查询的答案。
示例 1:
输入:queries = [[1,3,7]]
输出:[4]
解释:
只有一个查询。
big_nums[1..3] = [2,1,2]
。它们的乘积为 4。结果为 4 % 7 = 4
。
示例 2:
输入:queries = [[2,5,3],[7,7,4]]
输出:[2,2]
解释:
有两个查询。
第一个查询:big_nums[2..5] = [1,2,4,1]
。它们的乘积为 8 。结果为 8 % 3 = 2
。
第二个查询:big_nums[7] = 2
。结果为 2 % 4 = 2
。
提示:
1 <= queries.length <= 500
queries[i].length == 3
0 <= queries[i][0] <= queries[i][1] <= 1015
1 <= queries[i][2] <= 105
AC代码
class Solution {
public:
int fastpow(long long x, long long m, long long mod) { //递归快速幂
if (mod == 1) return 0; //特例
if (m == 0) return 1;
long long re = fastpow(x, m / 2, mod);
if (m % 2) return re * re * x % mod;
else return re * re % mod;
}
long long psum(long long p) {
long long re = 0, n = 0, cnt = 0, sum = 0;
for (long long i = __lg(p + 1); i >= 0; i--) { //__lg取二进制最高位的1
long long num = (cnt << i) + (i << i >> 1); // 新增的幂次个数
if (num <= p) {
p -= num;
re += (((i * (i - 1)) << i >> 2) + (sum << i));
sum += i; // 之前填的 1 的幂次之和
cnt++; // 之前填的 1 的个数
n |= 1LL << i; // 填 1, 1LL临时扩容
}
}
while (p--) {
re += __builtin_ctzll(n); //返回二进制末尾0的个数
n &= n - 1; // 去掉最低位的 1(置为 0)
}
return re;
}
vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
vector<int> ans;
for (auto& q : queries) {
auto l = psum(q[0]);
auto r = psum(q[1] + 1);
ans.push_back(fastpow(2, r - l, q[2]));
}
return ans;
}
};
标签:乘积,nums,big,long,力扣,re,3145,数组,queries
From: https://blog.csdn.net/2302_80216196/article/details/141638968