题目描述
B进制数，每个数字i(i=0,1,...,B-1)有a[i]个。你要用这些数字组成一个最大的B进制数X(不能有前导零，不需要用完所有数字)，使得X是B-1的倍数。q次询问，每次询问X在B进制下的第k位数字是什么(最低位是第0位)。
输入
第一行包含两个正整数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)，表示一个询问。
输出
输出q行，每行一个整数，依次回答每个询问，如果那一位不存在，请输出-1。
样例输入
3 3
1 1 1
0
1
2
样例输出
0
2
-1
题解
二分
一个比较常用的结论：当$k|b-1$（即$k$是$b-1$的约数）时，若$b$进制下某数的每一位之和是$k$的倍数，则该数是$k$的倍数。
在此题中，要求$X$是$B-1$的倍数，即$X$的每一位是$B-1$的倍数。
由于要让$X$尽量大，因此应该让其位数尽可能的多。由于保证了$a[i]ge 1$，因此可以先选出所有的数，在减掉多出来的一个数。这时需要注意：如果不多出来则不需要减去“0”。
然后倒序求前缀和，询问时二分即可。
时间复杂度$O(B+qlog B)$
#include <cstdio>
#include <algorithm>
using namespace std;
long long sum[1000010];
int main()
{
int n , m , i;
long long k , s = 0;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &sum[i]) , s += (i - 1) * sum[i] , sum[i] += sum[i - 1];
if(s % (n - 1))
for(i = s % (n - 1) + 1 ; i <= n ; i ++ )
sum[i] -- ;
while(m -- )
{
scanf("%lld" , &k);
if(k >= sum[n]) puts("-1");
else printf("%d
" , lower_bound(sum + 1 , sum + n + 1 , k + 1) - sum - 1);
}
return 0;
}