cogs2060 除法表達式【解法一】

【題目描述】

經過無盡的蘑菇和無盡的不知道錯在哪裡、不知道發生了什麼隻下，恭喜KZ成功的造出了資料！！可喜可賀可喜可賀

給出一個這樣的除法表達式：X1/X2/X3/X4/X5/X6…./Xk,

正常的除法表達式是從左往右計算的，但是我們可以向其中添加括号，以改變它的運算順序，如1/2/1/2=1/4 ,

(1/2)/(1/2)=1 ;

那麼， 給定一個除法表達式，能否通過添加括号使它的值為正整數？

【輸入格式】

多行

每行一個 除法表達式 【輸出格式】

多行

對應輸入，分别輸出“YES”（能為正整數）或“NO”（不能為正整數）

解法二見【這裡】。

很容易看出來，把原式寫成x1/(x2/x3/x4…/xn)是最好的結果，這樣把除了x2的數放在了分母上。接下來用其他數對x2求gcd進行約分即可。

#include<cstdio>
#include<cstring>
char s[];
int gcd(int x,int y)
{
    if (x<y)
    {
        int t=x;
        x=y;
        y=t;
    }
    if (y==) return x;
    return gcd(y,x%y);
}
int main()
{
    freopen("baoquansl.in","r",stdin);
    freopen("baoquansl.out","w",stdout);
    int i,j,k,l,m,n,p,q,x,y,z;
    while (scanf("%s",s+)==)
    {
        l=strlen(s+);
        y=;
        for (i=;s[i]>='0'&&s[i]<='9';i++)
          y=y*10+s[i]-'0';
        x=;
        for (i++;s[i]>='0'&&s[i]<='9';i++)
          x=x*10+s[i]-'0';
        x/=gcd(x,y);
        y=;
        for (i++;i<=l;i++)
          if (s[i]>='0'&&s[i]<='9')
            y=y*10+s[i]-'0';
          else
          {
            x/=gcd(x,y);
            y=;
          }
        x/=gcd(x,y);
        if (x==) printf("YES\n");
        else printf("NO\n");
    }
}