标签：数论，二分
题目
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],…,aB-1。 接下来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-1整除，则它在B进制下各个位置的和一定能被B-1整除
然后删去那个余数，做一遍前缀和，二分查询答案即可
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
#define mid ((l+r)>>1)
const int maxn=1e6+6;
ll a[maxn],s=0;int B,Q;
int main()
{
B=read(),Q=read();
rep(i,0,B-1){
a[i]=read();
s=(s+a[i]*i)%(B-1);
}
if(s)a[s]--;
rep(i,1,B-1)a[i]+=a[i-1];
while(Q--){
ll x=read()+1;
int ans=-1,l=0,r=B-1;
while(l<=r){
if(a[mid]>=x)ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
