# Bzoj4724 [poi2017]podzielno

## 结论题

Posted by yjjr's blog on April 6, 2018

# 题目

## Description

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

## Sample Input

3 3
1 1 1
0
1
2


## Sample Output

0
2
-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;
}