除法表达式

Time Limit(Common/Java):1000MS/10000MS Memory Limit:65536KByte
Total Submit: 279 Accepted: 68
Description
给出如下除法表达式E：X1/X2/X3/…./Xk
其中Xi是正整数并且Xi<=2 000 000 000(1<=i<=k,k<=10 000)。除法表达式应当按照从左到右的顺序求结果，例如
表达式1/2/1/2的值是1/4。现在让你可以在表达E中嵌入括号以改变计算顺序，例如表达式(1/2)/(1/2)的值是1。现在给你一个除法表达式E，要求告诉是否能够通过加括号（或者不加）得到表达式E’ ，E’的值为整数。
Input
输入数据包括多组数据，每组数据占一行，给出的是题目描述的表达式E，E中不含空格。
Output
每个测试数据占一行如果能找到题目中描述的E’ 则输出”YES”（不含引号），否则输出”NO” (不含引号)。
Sample Input
1/2/1/2
2/3
Sample Output
YES
NO
Source
TOJ
Uploader
crq

思路：
本题中，无论如何加括号，$X_1$都是分子，$X_2$都是分母，而加括号的唯一作用就是将$X_3$之后的数由分母变为分子，并且是任意选择的。那么本题的目标是将表达式结果转为整数，那么显然，要将尽量多的分母转为分子（只有除法才可能产生小数），那就是将所有的$X_3$及之后的分母转为分子。因此得到表达式：

$$E=\frac{X_1\prod_{i=3}^k(X_i)}{X_2}$$

那为了判断表达式$E$是否为整数，就将$X_2$于其余$X_i$值相约，看$X_2$最终能否被约成1即可。

代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

string expression;
int number[10001];
int InitNumber() {
	int Cnt = -1, temp = 0;
	for (const char& el : expression) {
		if (el == '/') {
			number[++Cnt] = temp;
			temp = 0;
		}
		else {
			temp *= 10;
			temp += el - '0';
		}
	}
	number[++Cnt] = temp;
	return Cnt;
}

//gcd(a,b)=gcd(b,a%b)
//gcd(a,0)=a
int gcd(int a, int b) {
	while (b) {
		int temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

void Compute(const int& Length) {

	number[1] /= gcd(number[1], number[0]);

	for (int i = 2; i <= Length; ++i) {
		number[1] /= gcd(number[i], number[1]);
	}
}

void Output(const int& Length) {

	if (Length == 0) {
		puts("Yes");
	}
	else {
		if (number[1] == 1) {
			puts("Yes");
		}
		else {
			puts("No");
		}
	}
}

int main(){

	cin >> expression;

	const int&& Length = InitNumber();

	Compute(Length);

	Output(Length);

	system("pause");
	return 0;

}