「BZOJ1385」「Baltic2000」Division expression 解题报告
2024-10-08 06:12:29
Division expression
Description
除法表达式有如下的形式: \(X_1/X_2/X_3.../X_k\) 其中Xi是正整数且\(X_i \le 1000000000(1 \le i \le k,K \le 10000)\) 除法表达式应当按照从左到右的顺序求,例如表达式1/2/1/2的值为1/4.但可以在表达式中加入括号来改变计算顺序,例如(1/2)/(1/2)的值为1.现给出一个除法表达式E,求是告诉是否可以通过增加括号来使其为E',E'为整数。
Input
先给出一个数字D,代表有D组数据. 每组数据先给出一个数字N,代表这组数据将有N个数。 接下来有N个数
Output
如果能使得表达式的值为一个整数,则输出YES.否则为NO
Sample Input
2
4
1
2
1
2
3
1
2
3
Sample Output
YES
NO
思路
观察这个式子\(E = X_1 / X_2 / X_3 .... / X_n\)
我们设\(E' = X_{a1} * X_{a2}..../ X_{b1} / X_{b2}....\)
即把加括号后的式子改成分数线的形式,有一些元素属于分子,其他的元素属于分母。
我们发现:
- \(X_1\) 不得不在分子 没有为什么 就是不可以
- \(X_2\) 不得不在分母 因为你想让它去分母它也不可能到分母
- \(X_3 \ to \ X_n\) 可在分子也可在分母 总是有办法的QAQ
如果叫你把\(X_3 \ to \ X_n\)分一部分在分子,其他的在分母,你会怎么做?? 当然是把全部元素放在分子呗。。。
因此最优的 \(E' = X_1 * X_3 * X_4....* X_n / X_2\)
如果真的乘起来的话肯定会溢出,所以当然要用GCD。
清爽的30行代码$(~ ̄▽ ̄)~ $
代码
#include<cstdio>
using namespace std;
#define MAXN 10005
int T;
int n, t, s;
int gcd( int x, int y ){
return x % y == 0 ? y : gcd( y, x % y );
}
int main(){
scanf( "%d", &T );
while( T-- ){
scanf( "%d", &n );
scanf( "%d", &t );
if ( n == 1 ){//注意特判
printf( "YES\n" ); continue;
}
scanf( "%d", &s );
s /= gcd( s, t );
for ( int i = 3; i <= n; ++i ){
scanf( "%d", &t );
s /= gcd( s, t );
}
if ( s == 1 ) printf( "YES\n" );
else printf( "NO\n" );
}
return 0;
}
最新文章
- Caffe.proto使用
- C语言中如何产生随机数
- Mysql相关集锦
- 防止IE7,8进入怪异模式
- 【原创】一起学C++ 之指针、数组、指针算术 ---------C++ primer plus(第6版)
- poj 2060 Taxi Cab Scheme (最小路径覆盖)
- 用分治法实现大数乘法,加法,减法(java实现)
- 实用lsof常用命令行
- 常用颜色大全---RGB值及中英文名称
- [转]Android Volley完全解析(四),带你从源码的角度理解Volley
- UOJ#117. 欧拉回路
- zoj 3981 Balloon Robot
- ng-model,ng-value,ng-bind,{{}}----angularJS数据绑定
- CF76A.Gift [最小生成树]
- Java软件工程师面试题:Java运行时异常与一般异常有什么不一样?
- 白盒测试实践-day03
- python三数之和
- google ctemplate——c++模板引擎
- (android高仿系列)今日头条 --新闻阅读器 (二)
- 发布上线前,先小秀一把俺的64位浏览器,速度那觉对是杠杠滴,上youtube,上google不费劲