BestCoder Round #54 (div.2) 1003 Geometric Progression-白红宇

BestCoder Round #54 (div.2) 1003 Geometric Progression

阅读量：6832 次

发布时间：2019-06-26

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

题意：判断是否是等比数列

分析：高精度 + 条件：a[i] * a[i+2] == a[i+1] * a[i+1]。特殊情况：0 0 0 0 0是Yes的，1 2 0 9 2是No的

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-9-5 20:06:46* File Name     :C.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e2 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const int numlen = 2005; // 需要的位数const int numbit = 4; // 数组一位表示的整数const int addbit = 10000;//进位数const int maxn = numlen/numbit + 10; // 数组要开的位数int max(int a, int b) { return a>b?a:b; }struct bign { int len, s[numlen]; bign() { memset(s, 0, sizeof(s)); len = 1; } bign(int num) { *this = num; } bign(const char *num) { *this = num; } bign operator = (const int num) { char s[numlen]; sprintf(s, "%d", num); *this = s; return *this; } bign operator = (const char *num) { int clen = strlen(num); while(clen > 1 && num[0] == '0') num++, clen--; len = 0; for(int i = clen-1;i >= 0;i -= numbit) { int top = min(numbit, i+1), mul = 1; s[len] = 0; for(int j = 0;j < top; j++) { s[len] += (num[i-j]-'0')*mul; mul *= 10; } len++; } deal(); return *this; } void deal() { while(len > 1 && !s[len-1]) len--; } bign operator + (const bign &a) const { bign ret; ret.len = 0; int top = max(len, a.len) , add = 0; for(int i = 0;add || i < top; i++) { int now = add; if(i < len) now += s[i]; if(i < a.len) now += a.s[i]; ret.s[ret.len++] = now%addbit; add = now/addbit; } return ret; } bign operator - (const bign &a) const { bign ret; ret.len = 0; int cal = 0; for(int i = 0;i < len; i++) { int now = s[i] - cal; if(i < a.len) now -= a.s[i]; if(now >= 0) cal = 0; else { cal = 1; now += addbit; } ret.s[ret.len++] = now; } ret.deal(); return ret; } bign operator * (const bign &a) const { bign ret; ret.len = len + a.len; for(int i = 0;i < len; i++) { int pre = 0; for(int j = 0;j < a.len; j++) { int now = s[i]*a.s[j] + pre; pre = 0; ret.s[i+j] += now; if(ret.s[i+j] >= addbit) { pre = ret.s[i+j]/addbit; ret.s[i+j] -= pre*addbit; } } if(pre) ret.s[i+a.len] = pre; } ret.deal(); return ret; } //乘以小数，直接乘快点 ***********注意计算过程可能会爆int bign operator * (const int num) { bign ret; ret.len = 0; int bb = 0; for(int i = 0;i < len; i++) { int now = bb + s[i]*num; ret.s[ret.len++] = now%addbit; bb = now/addbit; } while(bb) { ret.s[ret.len++] = bb % addbit; bb /= addbit; } ret.deal(); return ret; } // 除以一个小整数 ***********注意计算过程可能会爆int bign operator / (const int a) const { bign ret; ret.len = len; int pre = 0; for(int i = len-1;i >= 0; i--) { ret.s[i] = (s[i] + pre*addbit)/a; pre = s[i] + pre*addbit - a*ret.s[i]; } ret.deal(); return ret; } bign operator % (const int a) const { bign b = *this / a; return *this - b*a; } bign operator += (const bign &a) { *this = *this + a; return *this; } bign operator -= (const bign &a) { *this = *this - a; return *this; } bign operator *= (const bign &a) { *this = *this * a; return *this; } bign operator /= (const int a) { *this = *this / a; return *this; } bign operator %= (const int a) { *this = *this % a; return *this; } bool operator < (const bign &a) const { if(len != a.len) return len < a.len; for(int i = len-1;i >= 0; i--) if(s[i] != a.s[i]) return s[i] < a.s[i]; return false; } bool operator > (const bign &a) const { return a < *this; } bool operator <= (const bign &a) const { return !(*this > a); } bool operator >= (const bign &a) const { return !(*this < a); } bool operator == (const bign &a) const { return !(*this > a || *this < a); } bool operator != (const bign &a) const { return *this > a || *this < a; } void print() { printf("%d", s[len-1]); for(int i = len-2;i >= 0; i--) { printf("%04d", s[i]); } puts(""); } string str() const { string ret = ""; for(int i = 0;i < len; i++) ret = char(s[i] + '0') + ret; return ret; }};istream& operator >> (istream &in, bign &x) { string s; in >> s; x = s.c_str(); return in;}ostream& operator << (ostream &out, const bign &x) { printf("%d", x.s[x.len-1]); for(int i = x.len-2;i >= 0; i--) printf("%04d", x.s[i]); return out;}bign a[N];int main(void) { int T; scanf ("%d", &T); while (T--) { int n; scanf ("%d", &n); for (int i=1; i<=n; ++i) cin >> a[i]; bool flag = true; int zero = 0; for (int i=1; i<=n; ++i) { if (a[i] == 0) { zero++; } } if (n == 1 || zero == n) { puts ("Yes"); continue; } if (zero > 0) { puts ("No"); continue; } else { for (int i=1; i<=n-2; ++i) { if (a[i] * a[i+2] != a[i+1] * a[i+1]) { flag = false; break; } } } puts (flag ? "Yes" : "No"); } return 0;}