【BZOJ4724】[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与B-1互质，所以X是B-1的倍数当且仅当X在B进制下的每一位加起来是B-1的倍数。（在循环之美那题里用到了这个结论，不过我只是看了看~）

然后我们肯定是先全都选，然后看总和%B是多少，然后看最少删掉几个数。一开始还想了想怎么删，后来发现a[i]>=1。。。就直接把那个数删了就行。

然后剩下的数，一定是从大到小一个一个排下来。特判：如果总和%B=0，则不用删！

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

int n,m;

ll v[1000010];

inline ll rd()

{

	ll ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),m=rd();

	int i,l,r,mid;

	for(i=0;i<n;i++)	v[i]=rd(),v[n]=(v[n]+i*v[i])%(n-1);

	if(v[n])	v[v[n]]--;

	for(i=1;i<n;i++)	v[i]+=v[i-1];

	for(i=1;i<=m;i++)

	{

		ll a=rd();

		l=0,r=n;

		while(l<r)

		{

			mid=(l+r)>>1;

			if(v[mid]>a)	r=mid;

			else	l=mid+1;

		}

		printf("%d\n",r==n?-1:r);

	}

	return 0;

}//9 11 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 10

巴特西

【BZOJ4724】[POI2017]Podzielno 数学+二分