cogs2060 除法表达式

http://blog.csdn.net/sdfzyhx/article/details/52254071

作为分母的数当然是越少越好。将x2作为分母，其他作为分子，不断约分，最后判断。

 1 /*by SilverN*/
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 const int mxn=1000000;
 9 char s[mxn];
10 int gcd(int a,int b){
11     if(!b)return a;
12     return gcd(b,a%b);
13 }
14 int main(){
15     int i,j;
16     while(scanf("%s",s+1)!=EOF){
17         int len=strlen(s+1);
18         int x1=0,x2=0;
19         for(i=1;s[i]>='0'&&s[i]<='9';i++)
20          x1=x1*10+s[i]-'0';
21         for(i++;s[i]>='0'&&s[i]<='9';i++)
22          x2=x2*10+s[i]-'0';
23         x2/=gcd(x1,x2);
24         x1=0;
25         for(i++;i<=len;i++){
26             if (s[i]>='0'&&s[i]<='9')
27                 x1=x1*10+s[i]-'0';
28             else{
29                 x2/=gcd(x1,x2);
30                 x1=0;
31             }
32         }
33         x2/=gcd(x1,x2);
34         if(x2==1)printf("YES
");
35         else printf("NO
");
36     }
37     return 0;
38 }