BZOJ4724 [POI2017]Podzielno

4724: [POI2017]Podzielno

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 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+;

long long a[N];

long long B,q;

long long f[N];

inline int read()

{

    bool f=;char CH;for(;!isdigit(c);CH)if(c=='-')f=;

    int x=;for(;isdigit(c);CH)x=(x<<)+(x<<)+c-;

    return f?-x:x;

}

int main()

{

//  cout<<read();

    long long tmp=;

    B=read();q=read();

    For(i,,B-)a[i]=read();

    For(i,,B-)

    tmp=(tmp+1LL*(a[i]%(B-))*i)%(B-);

    if (tmp)a[tmp]--;

    f[]=a[];

    For(i,,B-)

    {

        f[i]=f[i-]+a[i];

    }

    while(q--)

    {

        long long k;scanf("%lld",&k);

        if(k>=f[B-])printf("-1");else

        printf("%d",lower_bound(f,f+B,k+)-f);

        puts("");

    }

    return ;

}

秒客网