nyoj1013 除法表达式
发布时间:2020-12-14 02:39:40 所属栏目:大数据 来源:网络整理
导读:题目:点击打开链接 ? 分析 :可易知, X 1一定在分子上, X 2一定在分母上,要想使E的结果为整数,即 X k尽量要在分子的上,可将E改写成: X 1/X2/(X3/X4/X5/X6.../Xk)=(X1*X3*X4*X5*X6...*Xk)/X2,现在简单了吧? ? 方法1:用大数相乘,再用大数求余 方
题目:点击打开链接 ? 分析:可易知,X1一定在分子上,X2一定在分母上,要想使E的结果为整数,即Xk尽量要在分子的上,可将E改写成:X1/X2/(X3/X4/X5/X6.../Xk)=(X1*X3*X4*X5*X6...*Xk)/X2,现在简单了吧? ? 方法1:用大数相乘,再用大数求余 方法2:从X1到Xk依次跟X2约分,知道X2为1时结束. ? 上码: #include<iostream> #include<cstdio> #include<vector> #include<algorithm> int gcd(int a,int b) { return b ? gcd(b,a % b) : a; } using namespace std; int main() { int nCase,n,x2; char c; bool is_integer; vector<int> myVector; cin >> nCase; while (nCase--) { myVector.clear(); while (1) { scanf("%d%c",&n,&c); myVector.push_back(n); if (c == 'n') { break; } } if (myVector.size() == 1) { is_integer = true; } else { x2 = myVector[1]; for (vector<int>::size_type i = 0; x2 != 1 && i < myVector.size(); i++) { if (i == 1) { continue; } x2 /= gcd(x2,myVector[i]); } x2 == 1 ? is_integer = true : is_integer = false; } is_integer ? cout << "YES" << endl : cout << "NO" << endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |