正题

题目链接:https://www.luogu.com.cn/problem/P5956

题目大意

(B)进制下，给出序列(a)，(a_i)表示数字(i)有多少个。求一个最大的(X)在(B)进制下，由给出的数字组成（不一定要用完），且其是(B-1)的倍数。

(q)次询问(X)的第(k)位是几。

(2leq Bleq 10^6,1leq qleq 10^5,1leq a_ileq 10^6,0leq kleq 10^{18})

解题思路

设(x_i)表示第(i)位的话就是

拆开单独的一个来看

所以其实就是各位数字的和为(B-1)的倍数就好了。

然后再回头看题目发现有限制(a_igeq 1)。这样如果用上所有数字的和对(B-1)取模为(t)的话，若(t)不为(0)，我们就让(a_t)减去一个(1)就好了。

然后对于询问求一个前缀和然后二分

时间复杂度(O(B+qlog B))

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10;
ll B,q,a[N];
signed main()
{
	scanf("%lld%lld",&B,&q);
	ll t=0;
	for(ll i=0;i<B;i++){
		scanf("%lld",&a[i]);
		(t+=a[i]*i)%=B-1;
	}
	if(t)a[t]--;
	for(ll i=0;i<B;i++)a[i]+=a[i-1];
	while(q--){
		ll x;scanf("%lld",&x);x++;
		if(x>a[B-1])puts("-1");
		else printf("%lldn",lower_bound(a,a+B,x)-a);
	}
	return 0;
}