bzoj1385: [Baltic2000]Division expression

歐幾里得算法。可以發現規律，a[2]作為分母，其他作為分子，必定是最好的選擇。判斷是否為整數即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
int read(){int x=0;char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();return x;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
int a[10005];
int main(){int cas=read();rep(i,1,cas){int n=read();a[1]=read();int temp=read();rep(i,2,n-1) a[i]=read();rep(i,1,n-1) {temp/=gcd(temp,a[i]);if(temp==1) {printf("YES\n");break;}}if(temp!=1) printf("NO\n");}return 0;
}

　　

1385: [Baltic2000]Division expression

Time Limit:?5 Sec??Memory Limit:?64 MB
Submit:?211??Solved:?142
[Submit][Status][Discuss]

Description

除法表達式有如下的形式: 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'為整數

Input

先給出一個數字D，代表有D組數據. 每組數據先給出一個數字N，代表這組數據將有N個數。 接下來有N個數

Output

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

Sample Input

2
4
1
2
1
2
3
1
2
3

Sample Output

YES
NO

HINT

Source

[Submit][Status][Discuss]