大数组元素的乘积

题目

大数组元素的乘积

---

一个整数 x 的 强数组 指的是满足和为 x 的二的幂的最短有序数组。比方说，11 的强数组为 [1, 2, 8] 。

我们将每一个正整数 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] <= 10^15
• 1 <= queries[i][2] <= 10^5

题解

方法一:

思路

观察在数字0到x中的二进制的规律

0 0 0 0 = 0
0 0 0 1 = 1
0 0 1 0 = 2
0 0 1 1 = 3
0 1 0 0 = 4
0 1 0 1 = 5
0 1 1 0 = 6
0 1 1 1 = 7
1 0 0 0 = 8
1 0 0 1 = 9
1 0 1 0 = 10
1 0 1 1 = 11
1 1 0 0 = 12
1 1 0 1 = 13
1 1 1 0 = 14
1 1 1 1 = 15

令二进制数$x=\overline{b_ib_{i-1}\cdots b_{1}b_{0}}$低位第i位是$b_i$

0到x二进制低位第0位，呈现0101010101...
0到x二进制低位第1位，呈现00110011...
0到x二进制低位第2位，呈现0000111100001111...
0到x二进制低位第3位，呈现00000000111111110000000011111111...

0到x二进制低位第i位，产生的连续的0或者1的区域有$block=\lfloor \frac{x+1}{2^i} \rfloor+1$ 个。如果有偶数块区域，那么最后一块的1的个数可能不足$2^i$个。
所以总共1的个数是$\lfloor \frac{block}{2} \rfloor \times 2^i$，如果$block$是奇数，那么需要额外加上最后一块的大小$(x+1)\bmod b$

我们只需$log(x)$可知0到x二进制某一位1的总和。也可以知道所有1的总和。此外知道第i位的1的数量该位上每一个1的贡献是$2^i$。

现在令$cnt_x$为0到x二进制上所有1的总和。显然$cnt_x$是随着x增长而增长，存在单调性。我们可以二分得到最大的x，使得$cnt_x < s$，然后在从低位到高位遍历x+1的二进制位，补齐到s位。从而将这s个1区分出不同权重的1的个数，便于计算总贡献。时间复杂度$loglogn$。

对于题目要求在范围[x,y]间的贡献，两次二分相减即可。

代码

class Solution {
public:
    using ll = long long;
    ll fpow(ll x, ll p, ll mod) {
        ll rt = 1;
        while (p) {
            if (p&1) rt *= x, rt %= mod;
            x *= x;
            x %= mod;
            p >>= 1;
        }
        return rt;
    }
    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
        auto cnt = [&](ll x)->ll { // 0 ~ x 的二进制的1的个数
            ll c = 0;
            for (int i=0; i<60; i++) {
                ll b = 1LL<<i;
                c += (x+1)/b/2*b + ((x+1)/b%2 ? (x+1)%b : 0);
                if (c>2e15) return 2e15;
            }
            return c;
        };
        auto cpu = [&](ll x, ll mod) { // 0 ~ x 各层位的二进制个数
            vector<ll> v(60);
            if (x == 0) return v;
            for (int i=0; i<60; i++) {
                ll b = 1LL<<i;
                ll c = (x+1)/b/2*b + ((x+1)/b%2 ? (x+1)%b : 0);
                v[i] = c;
            }
            return v;
        };
        auto ps = [&](ll x, ll mod) { // big_nums前x个，各2幂次的个数
            ll l = 0, r = x+1;
            while (l < r) {
                ll m = l+r>>1;
                if (cnt(m) <= x) {
                    l = m+1;
                } else {
                    r = m;
                }
            }
            // cnt(r) 是大于 x 的最小r
            // cnt(r-1) <= x < cnt(r)
            ll need = x-cnt(r-1);
            auto ans = cpu(r-1, mod);
            if (need == 0) return ans;
            
            for (int i=0; i<60; i++) {
                if (r>>i&1) {
                    ans[i]++;
                    if (--need == 0) return ans;
                }
            }
            return ans;
        };
        vector<int> ans;

        for (auto& x:queries) {
            ll l = x[0]+1, r = x[1]+1, mod = x[2];
            auto p = ps(r, mod);
            auto q = ps(l-1, mod);
            ll rt = 1;
            for (int i=0; i<60; i++) {
                ll b = 1LL<<i;
                rt *= fpow(b%mod, p[i]-q[i], mod);
                rt %= mod;
            }
            ans.push_back(rt);
        }
        return ans;
    }
};