题解：构造能被B-1整除的最大B进制数

问题分析

题目要求在给定基数B下，使用给定数量的数字卡片，构造一个能被B-1整除的最大数，并回答关于该数特定位置的查询。核心挑战在于：

1. 利用B进制数的整除特性（能被B-1整除等价于各位数字和能被B-1整除）
2. 构造最大数（尽可能多的数字，且高位数字尽可能大）
3. 高效处理大规模查询（位置可能达1e18）

关键 insights

1. 整除特性：对于基数B，任何数 mod (B-1) 等于其各位数字和 mod (B-1)。因此，只需保证数字和能被B-1整除即可。
2. 最大数构造策略：
   • 优先使用所有可用数字（数量最多）
   • 若数字和不能被B-1整除，移除最小的必要数字（使剩余和能被B-1整除）
   • 剩余数字按降序排列（确保高位最大）
3. 查询处理：通过前缀和+二分查找，快速定位任意位置的数字，避免存储完整大数。

算法步骤

1. 计算总和与总数：

   • 计算所有数字的总和S和总数量T
   • 计算S mod (B-1) 得到余数R

2. 调整数字集：

   • 若R=0：直接使用所有数字
   • 若R≠0：移除一个数字x（x≡R mod (B-1)），优先选择最小的x（减少对大数构造的影响）

3. 预处理有效数字：

   • 保留数量>0的数字，按降序排列
   • 计算前缀和数组，用于快速定位位置

4. 处理查询：

   • 对于位置k：若k≥总位数，返回-1
   • 否则计算k在降序序列中的偏移量，通过二分查找前缀和定位对应数字

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int B, q;
    cin >> B >> q;
    vector<long long> a(B);
    for (int i = 0; i < B; ++i) {
        cin >> a[i];
    }
    
    // 计算数字总和S和总数量T
    long long S = 0;
    long long T = 0;
    for (int i = 0; i < B; ++i) {
        S += 1LL * i * a[i];
        T += a[i];
    }
    
    int M = B - 1;
    int R = S % M;
    if (R < 0) R += M;  // 确保余数非负
    
    // 确定需要移除的数字x_remove
    bool need_remove = (R != 0);
    int x_remove = -1;
    if (need_remove) {
        // 优先找x ≡ R mod M且x >= R（最小可能的x）
        for (int x = R; x < B; x += M) {
            if (a[x] > 0) {
                x_remove = x;
                break;
            }
        }
        // 若未找到，找x = R - M（等价于x ≡ R mod M）
        if (x_remove == -1) {
            x_remove = R - M;
        }
    }
    
    // 预处理有效数字及其前缀和
    vector<int> digits;         // 降序存储有效数字
    vector<long long> prefix;   // 前缀和数组
    long long total = 0;        // 总位数
    
    for (int d = B - 1; d >= 0; --d) {
        long long cnt = a[d];
        if (need_remove && d == x_remove) {
            cnt -= 1;  // 移除一个x_remove
        }
        if (cnt > 0) {
            digits.push_back(d);
            total += cnt;
            prefix.push_back(total);
        }
    }
    
    // 处理全零特殊情况（仅保留一个0）
    bool all_zero = true;
    for (int d : digits) {
        if (d != 0) {
            all_zero = false;
            break;
        }
    }
    if (all_zero) {
        digits = {0};
        prefix = {1};
        total = 1;
    }
    
    // 处理查询
    while (q--) {
        long long k;
        cin >> k;
        if (k >= total) {
            cout << -1 << '\n';
            continue;
        }
        
        // 计算在降序序列中的索引（从左到右）
        long long idx = total - 1 - k;
        
        if (all_zero) {
            cout << 0 << '\n';
            continue;
        }
        
        // 二分查找定位数字
        auto it = upper_bound(prefix.begin(), prefix.end(), idx);
        int pos = it - prefix.begin();
        cout << digits[pos] << '\n';
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：O(B + q log C)，其中B为基数，q为查询数，C为有效数字种类数（C ≤ B）
• 空间复杂度：O(B)，用于存储数字计数和前缀和数组

该方案高效处理了大规模输入和查询，通过数学特性优化构造逻辑，结合二分查找实现快速查询响应。