[BZOJ1385] [Baltic2000] Division expression

題面

除法表達式有如下的形式: X1/X2/X3.../Xk 其中Xi是正整數且Xi<=1000000000(1<=i<=k,K<=10000) 除法表達式應當按照從左到右的順序求，例如表達式1/2/1/2的值為1/4.但可以在表達式中國入括弧來改變計算順序，例如(1/2)/(1/2)的值為1.現給出一個除法表達式E，求是告訴是否可以通過增加括弧來使其為E',E'為整數。

輸入格式

先給出一個數字D，代表有D組數據. 每組數據先給出一個數字N，代表這組數據將有N個數。 接下來有N個數，分別代表X1，X2，X3，...，XN。

輸出格式

如果能使得表達式的值為一個整數，則輸出YES.否則為NO。

樣例

2
4
1
2
1
2
3
1
2
3

YES
NO

思路

打個比方，x1/x2/x3=x1/(x2/x3)=x1*x3/x2

易證得x2定為分母，只要其他數都能被s2整除即可(gcd).

代碼

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long n,t,s[100000],sum;
 4 int main(){
 5     cin>>n;
 6     while (n--){
 7         cin>>t;
 8         for (int i=1;i<=t;i++) cin>>s[i];
 9         for (int i=1;i<=t;i++) if (i!=2)s[2]/=__gcd(s[i],s[2]);
10         if (s[2]==1) cout<<"YES\n";else cout<<"NO\n";
11     }
12     return 0;
13 }