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位)。

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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr