BZOJ 4724: [POI2017]Podzielno(数学+二分)

Description

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

Input

第一行包含两个正整数B(2<=B<=10^6),q(1<=q<=10^5)。
第二行包含B个正整数a[0],a[1],a[2],…,a[B-1](1<=a[i]<=10^6)。
接下来q行,每行一个整数k(0<=k<=10^18),表示一个询问。

Output

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

Sample Input

3 3
1 1 1
0
1
2

Sample Output

0
2
-1
思路:对于一个B进制数,假设他的某一位为a,那么就相当于,然后,通过二项式展开,.所以说这个题目就是说让你求一个最大的B进制数满足它的各位相加是B-1的倍数。
因为a[i]均大于1,那么如果所有的数加起来模上一个B-1不等于0,那我们就把那个数删掉。做完这一切后,相当于我们已经把题目要求的数求出来了。
因为要最大,所以肯定要把越大的数往更高的位置放。所以维护一个前缀和,满足了单调性,然后二分答案。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注