岳阳做网站公司,爱站网收录,企业在线购物网站建设,河南app定制4724: [POI2017]Podzielno Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 77 Solved: 37[Submit][Status][Discuss]Description B进制数，每个数字i(i0,1,...,B-1)有a[i]个。你要用这些数字组成一个最大的B进制数X(不能有前导零，不需要用完所有数字)…
Submit: 77 Solved: 37
[Submit][Status][Discuss]
1 1 1
0
1
2
2
-1[Submit][Status][Discuss]
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 31 1 1
0
1
2
Sample Output
02
-1
HINT
Source
鸣谢Claris上传
-----------------------------------------------------------------------------
数学题目
证明在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");elseprintf("%d",lower_bound(f,f+B,k+1)-f);puts("");}return 0;
}
转载于:https://www.cnblogs.com/rwy233/p/6188045.html