bzoj4724 [ POI2017 ] --数论

2018-06-17 23:28:01来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目大意:

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:用C++实现的贪吃蛇游戏

下一篇:EC笔记:第4部分:18、接口正确使用,不易被误用