hdu 5429 Geometric Progression（存个大数模板）-白红宇

hdu 5429 Geometric Progression（存个大数模板）

阅读量：5097 次

发布时间：2019-06-13

本文共 17443 字，大约阅读时间需要 58 分钟。

Problem Description

Determine whether a sequence is a Geometric progression or not.In mathematics, a **geometric progression**, also known as a **geometric sequence**, is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. For example, the sequence 2, 6, 18, 54, ... is a geometric progression with common ratio 3. Similarly 10, 5, 2.5, 1.25, ... is a geometric sequence with common ratio 1/2.Examples of a geometric sequence are powers rk of a fixed number r, such as 2k and 3k. The general form of a geometric sequence isa, ar, ar2, ar3, ar4, …where r ≠ 0 is the common ratio and a is a scale factor, equal to the sequence's start value.

Input

First line contains a single integer T(T≤20) which denotes the number of test cases. For each test case, there is an positive integer n(1≤n≤100) which denotes the length of sequence,and next line has n nonnegative numbers Ai which allow leading zero.The digit's length of Ai no larger than 100.

Output

For each case, output "Yes" or "No".

Sample Input

4 1 0 3 1 1 1 3 1 4 2 5 16 8 4 2 1

Sample Output

Yes Yes No Yes

Source

判定一个序列是否是等比数列。

坑点：

首项可以是0，此时其余项必须全为0才是等比数列

扒了个比较好用的大数模板，几乎可以和int一样使用。

1 #include 
      
         2 #include 
       
          3 using namespace std;  4   5 #define DIGIT   4      //四位隔开,即万进制  6 #define DEPTH   10000        //万进制  7 #define MAX     251    //题目最大位数/4，要不大直接设为最大位数也行  8 typedef int bignum_t[MAX+1];  9  10 /************************************************************************/ 11 /* 读取操作数，对操作数进行处理存储在数组里                             */ 12 /************************************************************************/ 13 int read(bignum_t a,istream&is=cin) 14 { 15     char buf[MAX*DIGIT+1],ch ; 16     int i,j ; 17     memset((void*)a,0,sizeof(bignum_t)); 18     if(!(is>>buf))return 0 ; 19     for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--) 20     ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ; 21     for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j
        
         1;a[0]--); 26     return 1 ; 27 } 28  29 void write(const bignum_t a,ostream&os=cout) 30 { 31     int i,j ; 32     for(os<
         
          =DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++); 56     return comp(a,c); 57 } 58  59 int comp(const bignum_t a,const int c,const int d,const bignum_t b) 60 { 61     int i,t=0,O=-DEPTH*2 ; 62     if(b[0]-a[0]
          
           d;i--) 65     { 66         t=t*DEPTH+a[i-d]*c-b[i]; 67         if(t>0)return 1 ; 68         if(t
           
            0)return 1 ; 74 if(t
            
             0 ; 77 } 78 /************************************************************************/ 79 /* 大数与大数相加 */ 80 /************************************************************************/ 81 void add(bignum_t a,const bignum_t b) 82 { 83 int i ; 84 for(i=1;i<=b[0];i++) 85 if((a[i]+=b[i])>=DEPTH) 86 a[i]-=DEPTH,a[i+1]++; 87 if(b[0]>=a[0]) 88 a[0]=b[0]; 89 else 90 for(;a[i]>=DEPTH&&i
             
              0); 92 } 93 /************************************************************************/ 94 /* 大数与小数相加 */ 95 /************************************************************************/ 96 void add(bignum_t a,const int b) 97 { 98 int i=1 ; 99 for(a[1]+=b;a[i]>=DEPTH&&i
              
               =DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);101 }102 /************************************************************************/103 /* 大数相减(被减数>=减数) */104 /************************************************************************/105 void sub(bignum_t a,const bignum_t b)106 {107 int i ;108 for(i=1;i<=b[0];i++)109 if((a[i]-=b[i])<0)110 a[i+1]--,a[i]+=DEPTH ;111 for(;a[i]<0;a[i]+=DEPTH,i++,a[i]--);112 for(;!a[a[0]]&&a[0]>1;a[0]--);113 }114 /************************************************************************/115 /* 大数减去小数(被减数>=减数) */116 /************************************************************************/117 void sub(bignum_t a,const int b)118 {119 int i=1 ;120 for(a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);121 for(;!a[a[0]]&&a[0]>1;a[0]--);122 }123 124 void sub(bignum_t a,const bignum_t b,const int c,const int d)125 {126 int i,O=b[0]+d ;127 for(i=1+d;i<=O;i++)128 if((a[i]-=b[i-d]*c)<0)129 a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH ;130 for(;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);131 for(;!a[a[0]]&&a[0]>1;a[0]--);132 }133 /************************************************************************/134 /* 大数相乘，读入被乘数a，乘数b，结果保存在c[] */135 /************************************************************************/136 void mul(bignum_t c,const bignum_t a,const bignum_t b)137 {138 int i,j ;139 memset((void*)c,0,sizeof(bignum_t));140 for(c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)141 for(j=1;j<=b[0];j++)142 if((c[i+j-1]+=a[i]*b[j])>=DEPTH)143 c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH ;144 for(c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);145 }146 /************************************************************************/147 /* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数 */148 /************************************************************************/149 void mul(bignum_t a,const int b)150 {151 int i ;152 for(a[1]*=b,i=2;i<=a[0];i++)153 {154 a[i]*=b ;155 if(a[i-1]>=DEPTH)156 a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH ;157 }158 for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);159 for(;!a[a[0]]&&a[0]>1;a[0]--);160 }161 162 void mul(bignum_t b,const bignum_t a,const int c,const int d)163 {164 int i ;165 memset((void*)b,0,sizeof(bignum_t));166 for(b[0]=a[0]+d,i=d+1;i<=b[0];i++)167 if((b[i]+=a[i-d]*c)>=DEPTH)168 b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH ;169 for(;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);170 for(;!b[b[0]]&&b[0]>1;b[0]--);171 }172 /**************************************************************************/173 /* 大数相除,读入被除数a，除数b，结果保存在c[]数组 */174 /* 需要comp()函数 */175 /**************************************************************************/176 void div(bignum_t c,bignum_t a,const bignum_t b)177 {178 int h,l,m,i ;179 memset((void*)c,0,sizeof(bignum_t));180 c[0]=(b[0]
               
                >1;h>l;m=(h+l+1)>>1)183 if(comp(b,m,i-1,a))h=m-1 ;184 else l=m ;185 for(;!c[c[0]]&&c[0]>1;c[0]--);186 c[0]=c[0]>1?c[0]:1 ;187 }188 189 void div(bignum_t a,const int b,int&c)190 {191 int i ;192 for(c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);193 for(;!a[a[0]]&&a[0]>1;a[0]--);194 }195 /************************************************************************/196 /* 大数平方根，读入大数a，结果保存在b[]数组里 */197 /* 需要comp()函数 */198 /************************************************************************/199 void sqrt(bignum_t b,bignum_t a)200 {201 int h,l,m,i ;202 memset((void*)b,0,sizeof(bignum_t));203 for(i=b[0]=(a[0]+1)>>1;i;sub(a,b,m,i-1),b[i]+=m,i--)204 for(h=DEPTH-1,l=0,b[i]=m=(h+l+1)>>1;h>l;b[i]=m=(h+l+1)>>1)205 if(comp(b,m,i-1,a))h=m-1 ;206 else l=m ;207 for(;!b[b[0]]&&b[0]>1;b[0]--);208 for(i=1;i<=b[0];b[i++]>>=1);209 }210 /************************************************************************/211 /* 返回大数的长度 */212 /************************************************************************/213 int length(const bignum_t a)214 {215 int t,ret ;216 for(ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);217 return ret>0?ret:1 ;218 }219 /************************************************************************/220 /* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数 */221 /************************************************************************/222 int digit(const bignum_t a,const int b)223 {224 int i,ret ;225 for(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);226 return ret%10 ;227 }228 /************************************************************************/229 /* 返回大数末尾0的个数 */230 /************************************************************************/231 int zeronum(const bignum_t a)232 {233 int ret,t ;234 for(ret=0;!a[ret+1];ret++);235 for(t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++);236 return ret ;237 }238 239 void comp(int*a,const int l,const int h,const int d)240 {241 int i,j,t ;242 for(i=l;i<=h;i++)243 for(t=i,j=2;t>1;j++)244 while(!(t%j))245 a[j]+=d,t/=j ;246 }247 248 void convert(int*a,const int h,bignum_t b)249 {250 int i,j,t=1 ;251 memset(b,0,sizeof(bignum_t));252 for(b[0]=b[1]=1,i=2;i<=h;i++)253 if(a[i])254 for(j=a[i];j;t*=i,j--)255 if(t*i>DEPTH)256 mul(b,t),t=1 ;257 mul(b,t);258 }259 /************************************************************************/260 /* 组合数 */261 /************************************************************************/262 void combination(bignum_t a,int m,int n)263 {264 int*t=new int[m+1];265 memset((void*)t,0,sizeof(int)*(m+1));266 comp(t,n+1,m,1);267 comp(t,2,m-n,-1);268 convert(t,m,a);269 delete[]t ;270 }271 /************************************************************************/272 /* 排列数 */273 /************************************************************************/274 void permutation(bignum_t a,int m,int n)275 {276 int i,t=1 ;277 memset(a,0,sizeof(bignum_t));278 a[0]=a[1]=1 ;279 for(i=m-n+1;i<=m;t*=i++)280 if(t*i>DEPTH)281 mul(a,t),t=1 ;282 mul(a,t);283 }284 285 #define SGN(x) ((x)>0?1:((x)<0?-1:0))286 #define ABS(x) ((x)>0?(x):-(x))287 288 int read(bignum_t a,int&sgn,istream&is=cin)289 {290 char str[MAX*DIGIT+2],ch,*buf ;291 int i,j ;292 memset((void*)a,0,sizeof(bignum_t));293 if(!(is>>str))return 0 ;294 buf=str,sgn=1 ;295 if(*buf=='-')sgn=-1,buf++;296 for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)297 ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;298 for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j
                
                 1;a[0]--);303 if(a[0]==1&&!a[1])sgn=0 ;304 return 1 ;305 }306 struct bignum307 {308 bignum_t num ;309 int sgn ;310 public :311 inline bignum()312 {313 memset(num,0,sizeof(bignum_t));314 num[0]=1 ;315 sgn=0 ;316 }317 inline int operator!()318 {319 return num[0]==1&&!num[1];320 }321 inline bignum&operator=(const bignum&a)322 {323 memcpy(num,a.num,sizeof(bignum_t));324 sgn=a.sgn ;325 return*this ;326 }327 inline bignum&operator=(const int a)328 {329 memset(num,0,sizeof(bignum_t));330 num[0]=1 ;331 sgn=SGN (a);332 add(num,sgn*a);333 return*this ;334 }335 ;336 inline bignum&operator+=(const bignum&a)337 {338 if(sgn==a.sgn)add(num,a.num);339 else if340 (sgn&&a.sgn)341 {342 int ret=comp(num,a.num);343 if(ret>0)sub(num,a.num);344 else if(ret<0)345 {346 bignum_t t ;347 memcpy(t,num,sizeof(bignum_t));348 memcpy(num,a.num,sizeof(bignum_t));349 sub (num,t);350 sgn=a.sgn ;351 }352 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;353 }354 else if(!sgn)355 memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn ;356 return*this ;357 }358 inline bignum&operator+=(const int a)359 {360 if(sgn*a>0)add(num,ABS(a));361 else if(sgn&&a)362 {363 int ret=comp(num,ABS(a));364 if(ret>0)sub(num,ABS(a));365 else if(ret<0)366 {367 bignum_t t ;368 memcpy(t,num,sizeof(bignum_t));369 memset(num,0,sizeof(bignum_t));370 num[0]=1 ;371 add(num,ABS (a));372 sgn=-sgn ;373 sub(num,t);374 }375 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;376 }377 else if378 (!sgn)sgn=SGN(a),add(num,ABS(a));379 return*this ;380 }381 inline bignum operator+(const bignum&a)382 {383 bignum ret ;384 memcpy(ret.num,num,sizeof (bignum_t));385 ret.sgn=sgn ;386 ret+=a ;387 return ret ;388 }389 inline bignum operator+(const int a)390 {391 bignum ret ;392 memcpy(ret.num,num,sizeof (bignum_t));393 ret.sgn=sgn ;394 ret+=a ;395 return ret ;396 }397 inline bignum&operator-=(const bignum&a)398 {399 if(sgn*a.sgn<0)add(num,a.num);400 else if401 (sgn&&a.sgn)402 {403 int ret=comp(num,a.num);404 if(ret>0)sub(num,a.num);405 else if(ret<0)406 {407 bignum_t t ;408 memcpy(t,num,sizeof(bignum_t));409 memcpy(num,a.num,sizeof(bignum_t));410 sub(num,t);411 sgn=-sgn ;412 }413 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;414 }415 else if(!sgn)add (num,a.num),sgn=-a.sgn ;416 return*this ;417 }418 inline bignum&operator-=(const int a)419 {420 if(sgn*a<0)add(num,ABS(a));421 else if(sgn&&a)422 {423 int ret=comp(num,ABS(a));424 if(ret>0)sub(num,ABS(a));425 else if(ret<0)426 {427 bignum_t t ;428 memcpy(t,num,sizeof(bignum_t));429 memset(num,0,sizeof(bignum_t));430 num[0]=1 ;431 add(num,ABS(a));432 sub(num,t);433 sgn=-sgn ;434 }435 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;436 }437 else if438 (!sgn)sgn=-SGN(a),add(num,ABS(a));439 return*this ;440 }441 inline bignum operator-(const bignum&a)442 {443 bignum ret ;444 memcpy(ret.num,num,sizeof(bignum_t));445 ret.sgn=sgn ;446 ret-=a ;447 return ret ;448 }449 inline bignum operator-(const int a)450 {451 bignum ret ;452 memcpy(ret.num,num,sizeof(bignum_t));453 ret.sgn=sgn ;454 ret-=a ;455 return ret ;456 }457 inline bignum&operator*=(const bignum&a)458 {459 bignum_t t ;460 mul(t,num,a.num);461 memcpy(num,t,sizeof(bignum_t));462 sgn*=a.sgn ;463 return*this ;464 }465 inline bignum&operator*=(const int a)466 {467 mul(num,ABS(a));468 sgn*=SGN(a);469 return*this ;470 }471 inline bignum operator*(const bignum&a)472 {473 bignum ret ;474 mul(ret.num,num,a.num);475 ret.sgn=sgn*a.sgn ;476 return ret ;477 }478 inline bignum operator*(const int a)479 {480 bignum ret ;481 memcpy(ret.num,num,sizeof (bignum_t));482 mul(ret.num,ABS(a));483 ret.sgn=sgn*SGN(a);484 return ret ;485 }486 inline bignum&operator/=(const bignum&a)487 {488 bignum_t t ;489 div(t,num,a.num);490 memcpy (num,t,sizeof(bignum_t));491 sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn ;492 return*this ;493 }494 inline bignum&operator/=(const int a)495 {496 int t ;497 div(num,ABS(a),t);498 sgn=(num[0]==1&&!num [1])?0:sgn*SGN(a);499 return*this ;500 }501 inline bignum operator/(const bignum&a)502 {503 bignum ret ;504 bignum_t t ;505 memcpy(t,num,sizeof(bignum_t));506 div(ret.num,t,a.num);507 ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn ;508 return ret ;509 }510 inline bignum operator/(const int a)511 {512 bignum ret ;513 int t ;514 memcpy(ret.num,num,sizeof(bignum_t));515 div(ret.num,ABS(a),t);516 ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a);517 return ret ;518 }519 inline bignum&operator%=(const bignum&a)520 {521 bignum_t t ;522 div(t,num,a.num);523 if(num[0]==1&&!num[1])sgn=0 ;524 return*this ;525 }526 inline int operator%=(const int a)527 {528 int t ;529 div(num,ABS(a),t);530 memset(num,0,sizeof (bignum_t));531 num[0]=1 ;532 add(num,t);533 return t ;534 }535 inline bignum operator%(const bignum&a)536 {537 bignum ret ;538 bignum_t t ;539 memcpy(ret.num,num,sizeof(bignum_t));540 div(t,ret.num,a.num);541 ret.sgn=(ret.num[0]==1&&!ret.num [1])?0:sgn ;542 return ret ;543 }544 inline int operator%(const int a)545 {546 bignum ret ;547 int t ;548 memcpy(ret.num,num,sizeof(bignum_t));549 div(ret.num,ABS(a),t);550 memset(ret.num,0,sizeof(bignum_t));551 ret.num[0]=1 ;552 add(ret.num,t);553 return t ;554 }555 inline bignum&operator++()556 {557 *this+=1 ;558 return*this ;559 }560 inline bignum&operator--()561 {562 *this-=1 ;563 return*this ;564 }565 ;566 inline int operator>(const bignum&a)567 {568 return sgn>0?(a.sgn>0?comp(num,a.num)>0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<0:0):a.sgn<0);569 }570 inline int operator>(const int a)571 {572 return sgn>0?(a>0?comp(num,a)>0:1):(sgn<0?(a<0?comp(num,-a)<0:0):a<0);573 }574 inline int operator>=(const bignum&a)575 {576 return sgn>0?(a.sgn>0?comp(num,a.num)>=0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<=0:0):a.sgn<=0);577 }578 inline int operator>=(const int a)579 {580 return sgn>0?(a>0?comp(num,a)>=0:1):(sgn<0?(a<0?comp(num,-a)<=0:0):a<=0);581 }582 inline int operator<(const bignum&a)583 {584 return sgn<0?(a.sgn<0?comp(num,a.num)>0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<0:0):a.sgn>0);585 }586 inline int operator<(const int a)587 {588 return sgn<0?(a<0?comp(num,-a)>0:1):(sgn>0?(a>0?comp(num,a)<0:0):a>0);589 }590 inline int operator<=(const bignum&a)591 {592 return sgn<0?(a.sgn<0?comp(num,a.num)>=0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<=0:0):a.sgn>=0);593 }594 inline int operator<=(const int a)595 {596 return sgn<0?(a<0?comp(num,-a)>=0:1):597 (sgn>0?(a>0?comp(num,a)<=0:0):a>=0);598 }599 inline int operator==(const bignum&a)600 {601 return(sgn==a.sgn)?!comp(num,a.num):0 ;602 }603 inline int operator==(const int a)604 {605 return(sgn*a>=0)?!comp(num,ABS(a)):0 ;606 }607 inline int operator!=(const bignum&a)608 {609 return(sgn==a.sgn)?comp(num,a.num):1 ;610 }611 inline int operator!=(const int a)612 {613 return(sgn*a>=0)?comp(num,ABS(a)):1 ;614 }615 inline int operator[](const int a)616 {617 return digit(num,a);618 }619 friend inline istream&operator>>(istream&is,bignum&a)620 {621 read(a.num,a.sgn,is);622 return is ;623 }624 friend inline ostream&operator<<(ostream&os,const bignum&a)625 {626 if(a.sgn<0)627 os<<'-' ;628 write(a.num,os);629 return os ;630 }631 friend inline bignum sqrt(const bignum&a)632 {633 bignum ret ;634 bignum_t t ;635 memcpy(t,a.num,sizeof(bignum_t));636 sqrt(ret.num,t);637 ret.sgn=ret.num[0]!=1||ret.num[1];638 return ret ;639 }640 friend inline bignum sqrt(const bignum&a,bignum&b)641 {642 bignum ret ;643 memcpy(b.num,a.num,sizeof(bignum_t));644 sqrt(ret.num,b.num);645 ret.sgn=ret.num[0]!=1||ret.num[1];646 b.sgn=b.num[0]!=1||ret.num[1];647 return ret ;648 }649 inline int length()650 {651 return :: length(num);652 }653 inline int zeronum()654 {655 return :: zeronum(num);656 }657 inline bignum C(const int m,const int n)658 {659 combination(num,m,n);660 sgn=1 ;661 return*this ;662 }663 inline bignum P(const int m,const int n)664 {665 permutation(num,m,n);666 sgn=1 ;667 return*this ;668 }669 };670 bignum a[105],zero;671 int main()672 {673 int i,t,n;674 zero=0;675 cin>>t;676 while(t--)677 {678 cin>>n;679 int cnt=0;680 for(i=0;i
                 
                  >a[i];683 if(a[i]==zero) ++cnt;684 }685 if(cnt&&cnt!=n) cout<<"No"<