当前位置: 代码迷 >> 综合 >> NYoj 1013 除法表达式
  详细解决方案

NYoj 1013 除法表达式

热度:40   发布时间:2023-12-06 08:18:35.0

题目:除法表达式

 

思路:

X1一定要做分子,X2一定要做分母,其余的数可做分母也可做分子。

若要整除,一定是尽量的把所有数都放到分子的位置。

然后就用欧几里得算法,把第二个数和其余的数约分,假如能约到1,那么就可能整除。

 

代码:

#include<bits/stdc++.h>
using namespace std;#define maxn 10000int n=0;
int a[maxn+5]= {0};void trn(string x){for(int i=0;i<x.size();i++){a[n]=a[n]*10+x[i]-'0';}
}void readin() {memset(a,0,sizeof(a));n=0;string x;int y;cin>>x;while(~(y=x.find("/"))) {string b=x.substr(0,y);x=x.substr(y+1);n++;trn(b);}n++;trn(x);
}int gcd(int x,int y){return y==0?x:gcd(y,x%y);
}bool slv(){swap(a[1],a[2]);for(int i=2;i<=n;i++) {a[1]/=gcd(a[1],a[i]);}return a[1]==1;
}int main() {int T;scanf("%d",&T);while(T--) {readin();if(slv()) printf("YES\n");else printf("NO\n");}return 0;
}