除法表达式
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
给出一个这样的除法表达式：X1/X2/X3/···/Xk，其中Xi是正整数。除法表达式应当按照从左到右的顺序求和，例如表达式1/2/1/2的值为1/4。但是可以在表达式中嵌入括号以改变计算顺序，例如表达式(1/2)/(1/2)的值为1.判断能否通过加括号使表达式的值为整数？？

输入
首先输入一个N，表示有N组测试数据，
每组数据输入占一行，为一个除法表达式，
输入保证合法。
使表达式的值为整数。k<=10000,Xi<=100000000.
输出
输出YES或NO
样例输入
1
1/2/1/2
样例输出
YES

定理一：
唯一分解定理：任何一个数都能写成素数相乘的形式：
X=p1^a1 *p2^a2 *p3^a3 *p4^a4…
定理二：
gcd(a,b)=gcd(b,a%b),
gcd(a,0)=a
用这两个定理可以轻松构造出辗转相除法
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);}
定理三：
gcd(a,b)*lcm(a,b)=a * b（这个我还没明白怎么证明的，改天找老师问一下）
lcm(a,b)=a * b / gcd(a,b) //a * b可能会溢出
lcm(a,b)=(a/gcd(a,b)) * b//防止溢出
辗转相除法的时间复杂度是logn
辗转相除法也称为欧几里得算法

这题判断它能不能整除，我们可以先将表达式改变形式为(x1x3x4*…*xn)/x2
然后只需要判断最后x2是否等于1，分母为1才整除，让后让x2每次和xi约分，约分只需要求gcd (x2,xi)就行了。

代码：（未ac，找不到平台）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int a[maxn];
int cnt;
bool __(){
	int g=__gcd(a[0],a[1]);
	a[1]/=g;
	for(int i=2;i<cnt;i++){
		if(a[1]==1)return true;
		a[1]/=__gcd(a[i],a[1]);
	}
	if(a[1]==1)return true;
	return false;
}
int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		memset(a,0,sizeof(a));
		char str[maxn*2];
		scanf("%s",str);
		str[strlen(str)]='/';
		int ans=0;cnt=0;
		for(int i=0;i<strlen(str);i++){
			if(str[i]=='/'){
				a[cnt++]=ans;
				ans=0;
			}else{
				ans=ans*10+(str[i]-48);
			}
		}
		int p=__();
		if(p){
			cout<<"YES"<<endl; 
		}else{
			cout<<"NO"<<endl;
		}
	}
	
}