HDU 5429 Geometric Progression

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 is

a, 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

3

1 1 1

3

1 4 2

5

16 8 4 2 1

Sample Output

Yes

Yes

No

Yes

#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 505;
int T, n, m;

struct bignum
{
    int s[maxn], len;
    char u[maxn];
    bignum(){ memset(s, 0, sizeof(s)); len = 0; }
    bool read()
    {
        scanf("%s", u);        
        int i, j = strlen(u);
        for (i = len = 0; u[i] == '0'; i++) j--;
        if (!u[i]) return false;
        for (i; u[i]; i++, len++) s[j--] = u[i] - '0';
        return true;
    }
}a[maxn];

bool operator !=(const bignum&a, const bignum&b)
{
    if (a.len != b.len) return true;
    for (int i = 1; i <= a.len; i++) if (a.s[i] != b.s[i]) return true;
    return false;
}

bignum operator *(const bignum&a, const bignum&b)
{
    bignum c;
    for (int i = 1; i <= a.len; i++)
        for (int j = 1; j <= b.len; j++)
            c.s[i + j - 1] += a.s[i] * b.s[j];
    c.len = a.len + b.len;
    for (int i = 1; i < c.len; i++)
    {
        c.s[i + 1] += c.s[i] / 10;
        c.s[i] %= 10;
    }
    while (c.s[c.len] == 0) c.len--;
    return c;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        int flag = 0;
        for (int i = 1; i <= n; i++) if (!a[i].read()) flag++;
        if (n == 1||n==flag) printf("Yes\n");
        else if (flag) printf("No\n");
        else 
        {
            if (n == 2) printf("Yes\n");
            else
            {
                for (int i = 1, j = 2, k = 3; k <= n; i++, j++, k++)
                    if (a[i] * a[k] != a[j] * a[j]) { flag++; break; }
                if (flag) printf("No\n"); else printf("Yes\n");
            }
        }
    }
    return 0;
}