BZOJ4724 [POI2017]Podzielno

4724: [POI2017]Podzielno

Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 77  Solved: 37[Submit][Status][Discuss]

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

HINT

 

Source

鸣谢Claris上传

[ Submit][ Status][ Discuss]

-----------------------------------------------------------------------------

数学题目 

证明在N进制下若1一个数是（N-1）的倍数 那么 他的每一位数字相加在（%(N-1)）的意义下等于 0

例如在10进制下 198是9的倍数 因为 （1+9+8）%9=0

证明：

　　假设一个数字A （N进制下） 那么设它每一位上的数字为 k[i] 则 A=Σki*N^i  (N^i)%(N-1)=1A%(N-1)=(Σki)%(N-1)=0

代码如下：

 

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define CH c=getchar() #define mp make_pair #define fi first #define se second #define For(i,x,y) for(int i=x;i<=y;++i) using namespace std; const int N=1e6+5; long long a[N]; long long B,q; long long f[N]; inline int read() { bool f=0;char CH;for(;!isdigit(c);CH)if(c=='-')f=1; int x=0;for(;isdigit(c);CH)x=(x<<1)+(x<<3)+c-48; return f?-x:x; } int main() { // cout<<read(); long long tmp=0; B=read();q=read(); For(i,0,B-1)a[i]=read(); For(i,0,B-1) tmp=(tmp+1LL*(a[i]%(B-1))*i)%(B-1); if (tmp)a[tmp]--; f[0]=a[0]; For(i,1,B-1) { f[i]=f[i-1]+a[i]; } while(q--) { long long k;scanf("%lld",&k); if(k>=f[B-1])printf("-1");else printf("%d",lower_bound(f,f+B,k+1)-f); puts(""); } return 0; }

 

转载于:https://www.cnblogs.com/rwy233/p/6188045.html

相关资源：数据结构—成绩单生成器