# 3145：大数组元素的乘积（2859 分） > **[力扣第 130 场双周赛第 4 题](https://leetcode.cn/problems/find-products-of-elements-of-big-array/)** ## 题目

一个非负整数 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。

提示：

## 分析 - 由于 big_nums 的数都是2的幂，令A[i]=log2(big_nums[i])，转为求 A的 [from,to] 区间和，令 g(a) 代表 A[:a] 的和，即转为求 g(to+1) 和 g(from) - 要求 g(a)，可以先二分找到 a 对应的最后整数 x - 先考虑这个问题：令 f(x) 代表 1到 x 所对应的强数组总长度，如何求 f(x) - f(x) 其实就是 1到x 的二进制位上 1 的总数， 这可以用贡献法解决： - 枚举每个二进制位 i，每 2^(i+1) 个数为一个循环，贡献 2^i 个 1，且都在后 2^i 个数，因此计算有多少个完整循环，并特判最后一个循环即可 - 于是二分找到第一个 x 使得 f(x)>=a，即是 a 对应的最后整数 - 接着求 g(a)，同样可以用贡献法： - 区别仅在于二进制位 i 上的权重位 2^i，因此算出个数后乘以 2^i 即可 - 注意最后整数 x 的强数组不一定完整，需要特判 ## 解答 ```python [] class Solution: def findProductsOfElements(self, queries: List[List[int]]) -> List[int]: def f(x): s = 0 for i in range(x.bit_length()): q,r = divmod(x,1<<(i+1)) s += q*(1<