除法表达式【数组】

除法表达式【数组】

时间： 1ms        内存：128M

描述：

给出如下除法表达式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'的值为整数。

输入：

输入数据包括多组数据，每组数据占一行，给出的是题目描述的表达式E，E中不含空格

输出：

每个测试数据占一行如果能找到题目中描述的E' 则输出"YES"（不含引号），否则输出"NO" (不含引号)。

示例输入：

1/3/1/3
2/3

示例输出：

YES
NO

提示：

参考答案（内存最优[1712]）：

#include<cstdio>  
#include<iostream>
using namespace std;  
int main()  
{  
    long long n,m=0,t;  
    char c;  
    while(cin>>n)  
    {  
        c=getchar();  
        if(c!='/'){cout<<"YES"<<endl;continue;}//这里要判断当只有一个整数的时候直接输出  
        cin>>t;                                 //t代表第一个分母  
        while(c=getchar()=='/')       
        {  
            n=n%t;  //分子%第一个分母  
            cin>>m;  
            n*=m;      
        }  
        if(n%t==0)cout<<"YES"<<endl;  
        else cout<<"NO"<<endl;  
    }  
    return 0;  
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<string.h>
int gcd(int a,int b)//公约数函数a<b（自己默认）
{
 int t;
 if(a>b)
 {
  t=a;
  a=b;
  b=t;
 }
 while(a!=0)
 {
  t=b;
  b=a;
  a=t%b;
 }
 return b;
}

char s[1100005];//注意字符串的程度，因为很大，所以放在外面宏定义
int main()
{
 int a[10005],i,j,k,s2,n,len,sum;
 while(gets(s))
 {
  len=strlen(s);
  if(len==1)
  {
  printf("YES\n");
  continue;
  }
  j=0;sum=0;
  for(i=0;i<len;i++)//把字符串里的数字一一取出来
  {
     if(s[i]!='/')
     sum=sum*10+(s[i]-'0');
     else
    {
     a[j++]=sum;
     sum=0;
    }
  }
  s2=a[1]/gcd(a[0],a[1]);
  for(i=2;i<=j;i++)
  {
   s2=s2/gcd(s2,a[i]);
   if(s2==1)
    break;
  }
  if(s2==1)
   printf("YES\n");
  else
   printf("NO\n");
 }
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。