首页 > 代码库 > cogs2060 除法表达式

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\n");35         else printf("NO\n");36     }37     return 0;38 }

 

cogs2060 除法表达式