bzoj4724--数论

2016-12-31 18:51:43来源:cnblogs.com作者:gjghfd人点击

题目大意:

B进制数,每个数字i(i=0,1,...,B-1)有a[i]个。你要用这些数字组成一个最大的B进制数X(不能有前导零,不需要用完所有数字),使得X是B-1的倍数。q次询问,每次询问X在B进制下的第k位数字是什么(最低位是第0位)。 思路:
由于如下定理:
a*Bk≡a( mod (B-1) ) 于是只要使所有位之和是(B-1)的倍数就可以了。又注意到a[i]>=1,只需删去sum%(B-1)就可以了。询问用二分。 代码:
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #define ll long long 6 char buf[100000],*p1=buf,*p2=buf; 7 inline char Nc(){ 8     if(p1==p2)p2=(p1=buf)+fread(buf,1,100000,stdin); 9     return *p1++;10 }11 inline void Read(ll& x){12     char c=Nc();13     for(;c<'0'||c>'9';c=Nc());14     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());15 }16 inline void Read(int& x){17     char c=Nc();18     for(;c<'0'||c>'9';c=Nc());19     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());20 }21 int i,j,n,m;22 ll a[1000001],k,Sum;23 inline int Find(ll k){24     int l=0,r=n-1,Mid;25     while(l<=r){26         Mid=l+r>>1;27         if(a[Mid]>=k)r=Mid-1;else l=Mid+1;28     }29     return l;30 }31 char s[20];32 int Len;33 inline void Print(int x){34     if(x==0){35         puts("0");36         return;37     }38     for(Len=0;x;x/=10)s[++Len]=x%10;39     for(;Len;)putchar(s[Len--]+48);40     puts("");41 }42 int main()43 {44     Read(n);Read(m);45     for(i=0;i<n;i++)Read(a[i]),Sum=Sum+a[i]*i;46     if(Sum%(n-1))a[Sum%(n-1)]--;47     for(i=1;i<n;i++)a[i]+=a[i-1];48     while(m--){49         Read(k);50         if(++k>a[n-1])puts("-1");else Print(Find(k));51     }52 }
bzoj4724

 

相关文章

    无相关信息

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台