[AdditionalFile4909.zip](file://AdditionalFile4909.zip?type=additional_file)

P5956 [POI 2017] Podzielno

题目描述

$B$ 进制数，每个数字 $i \in [0,B)$ 有 $a_i$ 个。你要用这些数字组成一个最大的 $B$ 进制数 $X$（不能有前导零，不需要用完所有数字），使得 $X$ 是 $B-1$ 的倍数。 $q$ 次询问，每次询问 $X$ 在 $B$ 进制下的第 $k$ 位数字是什么（最低位是第 $0$ 位）。

输入格式

第一行包含两个正整数 $B,q$。

第二行包含 $B$ 个正整数 $a_0,a_1,a_2,...,a_{B-1}$。

接下来 $q$ 行，每行一个整数 $k$，表示一个询问。

输出格式

输出 $q$ 行，每行一个整数，依次回答每个询问，如果那一位不存在，请输出 $-1$。

输入输出样例 #1

输入 #1

3 3
1 1 1
0
1
2

输出 #1

0
2 
-1

说明/提示

对于 $100\%$ 的数据，$2\le B\le10^6$，$1\le q\le 10^5$，$1\le a_i\le10^6$，$0\le k\le10^{18}$。

#4909. 「POI2017 R1」整除性 Divisibility

标签: 传统 | 时间限制: 2500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Podzielność

最近，Bajtuś 在计算机课上学到了位置计数法。他了解到，人类常用十进制，电脑用二进制，但其实任何大于 1 的自然数 $B$ 都可以作为计数基础。在这样的系统中，可用数字是 $0, 1, 2, \ldots, B-2, B-1$，一个 $k$ 位数 $c_{k-1} c_{k-2} \ldots c_{2} c_{1} c_{0}$ 表示：

$$c_{k-1} \cdot B^{k-1} + c_{k-2} \cdot B^{k-2} + \ldots + c_{2} \cdot B^{2} + c_{1} \cdot B + c_{0}$$

比如，在三进制中，$201$ 表示 $2 \cdot 3^{2} + 0 \cdot 3 + 1$，也就是十进制的 $19$（简写为 $201_{3} = 19_{10}$）。

Bajtuś 选了个数 $B$ 作为计数基础，把所有可用数字写在卡片上，有些数字可能重复：对于 $i = 0, 1, \ldots, B-1$，他有 $a_{i}$ 张写着 $i$ 的卡片。他想用这些卡片拼出尽可能大的、能被 $B-1$ 整除的数。请你写个程序帮他实现这个目标。这数可能很大，Bajtuś 只想知道某些特定位置的数字即可。注意，正数的写法不能以 $0$ 开头，$0$ 的唯一写法是 $0$。

特别说明：若基础 $B$ 超过 $10$，假设数字间有空格分隔，避免混淆。

输入格式

输入第一行包含两个整数 $B$ 和 $q$ $(B \geq 2, q \geq 1)$，用空格分隔，分别表示计数基础和查询次数。

第二行包含 $B$ 个整数 $a_{0}, a_{1}, \ldots, a_{B-1}$ $(a_{i} \geq 1)$，用空格分隔，表示 Bajtuś 拥有的每个数字 $i$ 的卡片数量。

接下来的 $q$ 行，每行一个整数 $k_{i}$ $(0 \leq k_{i} \leq 10^{18})$，表示查询目标数的第 $k_{i}$ 位。

输出格式

输出 $q$ 行，第 $i$ 行给出目标数（用 $B$ 进制表示、能被 $B-1$ 整除的最大数）的第 $k_{i}$ 位。位数从右往左数（最低位为 $0$）。若目标数位数少于 $k_{i}$，输出 $-1$。

样例

输入

3 3
1 1 1
0
1
2

输出

0
2
-1

在三进制中，有一张 $0$、一张 $1$ 和一张 $2$ 的卡片，可拼出：$0_{3} = 0_{10}$、$1_{3} = 1_{10}$、$2_{3} = 2_{10}$、$10_{3} = 3_{10}$、$12_{3} = 5_{10}$、$20_{3} = 6_{10}$、$21_{3} = 7_{10}$、$102_{3} = 11_{10}$、$120_{3} = 15_{10}$、$201_{3} = 19_{10}$、$210_{3} = 21_{10}$。能被 $2$ 整除的有 $0_{3}$、$2_{3}$、$20_{3}$，最大数是 $20_{3}$。

附加样例

1. $B=10, a_{i}=1, q=10, k_{i}=i-1$；
2. $B=2, a_{0}=10000, a_{1}=1, q=10001, k_{i}=i-1$；
3. $B=1000000, a_{i}=1, q=1, k_{1}=999999$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$B, a_{i}, q \leq 100$	$30$
$2$	$B, a_{i} \leq 100, q \leq 100000$	$25$
$3$	$B \leq 1000, a_{i} \leq 1000000, q \leq 1000$	$25$
$4$	$B, a_{i} \leq 1000000, q \leq 100000$	$20$