題目大意： 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進位數，每個數字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
