题目描述 定义数 xx 在 BB 进制下的一次操作为以下两种操作中的任意一种： 令 x \rightarrow \lfloor \dfrac{x}{B} \rfloorx→⌊ B x ​ ⌋。 令 x \rightarrow x \times B + tx→x×B+t。其中 t \in [0,B-1]t∈[0,B−1]。 现给定长度为 nn 的序列 AA。mm 次询问，每次询问形如： l r B 表示询问将序列 AA 中下标在 [l,r][l,r] 之内的数在 BB 进制下操作，至少多少次才能将所有数变为相同（注：每次操作是对一个数进行操作）。 询问间相互独立，即操作不会真的进行。 输入格式 第一个两个整数，分别表示 n,mn,m。 第二行一行 nn 个数，表示序列 AA。 接下来 mm 行，每行三个数，分别表示这次询问的 l,r,Bl,r,B。 输出格式 输出共 mm 行，其中第 ii 行表示第 ii 次询问的答案。 输入输出样例 输入 #1复制 5 5 7 6 5 8 9 1 3 2 2 5 2 4 4 6 3 5 4 1 5 3 输出 #1复制 5 8 0 5 10 输入 #2复制 8 4 10 14 7 11 19 13 7 18 1 7 4 3 8 2 1 4 4 1 4 2 输出 #2复制 15 18 8 11 说明/提示 样例解释 对于样例一，五次询问分别将区间内所有数变为 33、44、88、44、66 是一种最优操作。 数据范围 「本题采用捆绑测试」 \operatorname{Subtask} 1(10\%)Subtask1(10%)：n,m \leq 1000n,m≤1000。 \operatorname{Subtask} 2(20\%)Subtask2(20%)：保证所有询问 B=2B=2。 \operatorname{Subtask} 3(40\%)Subtask3(40%)：n,m \leq 3 \times 10^4n,m≤3×10 4 。 \operatorname{Subtask} 4(30\%)Subtask4(30%)：无特殊限制。 对于 100\%100% 的数据：1 \leq n,m \leq 10^51≤n,m≤10 5 ，2 \leq A_i,B \leq 10^82≤A i ​ ,B≤10 8 。c++代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

const int N = 1e5 + 10, M = 65;

int n, m;
LL a[N], s[N][M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int j = 0; j < M; j ++ ) s[n + 1][j] = 1;
    for (int i = n; i; i -- )
        for (int j = 0; j < M; j ++ )
        {
            s[i][j] = s[i + 1][j] * (a[i] % 2 + 1);
            a[i] /= 2;
        }

    while (m -- )
    {
        int l, r, B;
        cin >> l >> r >> B;

        int k = 0;
        while (B)
        {
            if (B & 1) k ++ ;
            B = B >> 1;
        }

        LL res = 1e18;
        for (int j = 0; j < M; j ++ )
        {
            if (k + j >= M) break;
            LL t = 0;
            for (int i = l; i <= r; i ++ ) t += s[i][j];
            res = min(res, t);
        }

        cout << res << endl;
    }

    return 0;
}