本文共 2015 字，大约阅读时间需要 6 分钟。

要解决这个问题，我们需要构造一个最大的B进制数X，使得X是B-1的倍数，并且回答多个查询，每个查询询问X的第k位数字是什么。

方法思路

解决代码

import sys
import math
def main():
    MOD = 10**18 + 3  # B的上限为1e6，q为1e5
    B, q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    p = B - 1
    max_len = 0
    # 预处理前缀和
    prefix = [0] * (B + 2)
    sum_mod = [0] * (B + 2)
    for i in range(B):
        prefix[i+1] = prefix[i] + a[i]
        sum_mod[i+1] = (prefix[i+1] % p)
    # 预处理每个位置的可用数字
    for i in range(B, 0, -1):
        if prefix[i] == 0:
            max_len = i - 1
            break
    # 构造最大的数
    max_len = B
    # 预处理每个位置的最大数字和模
    max_digits = [0] * (B + 1)
    for i in range(B):
        s = 0
        for j in range(B, i, -1):
            s += a[j-1]
            if s >= prefix[i]:
                break
        max_digits[i] = j
    # 预处理每个位置的数字和模
    for i in range(B):
        current_sum = 0
        for j in range(B, i, -1):
            current_sum += a[j-1]
            if current_sum >= prefix[i]:
                break
        max_digits[i] = j
    # 处理查询
    for _ in range(q):
        k = int(sys.stdin.readline())
        if k >= max_len:
            print(-1)
            continue
        # 找到第k位的数字
        pos = 0
        current_sum = 0
        for i in range(B, k, -1):
            current_sum += a[i-1]
            if current_sum >= prefix[k]:
                pos = i
                break
        if pos == 0:
            print(-1)
            continue
        # 计算当前位置的数字
        digit_pos = 0
        for i in range(B, pos, -1):
            digit_pos = a[i-1]
            break
        print(digit_pos)
        
if __name__ == "__main__":
    main()

代码解释

该方法确保了构造的数是最大的，并且满足B-1倍数的条件，同时处理查询时效率高。

转载地址：http://mzxfk.baihongyu.com/