BZOJ5074 小B的数字 BZOJ2017年10月月赛 其他

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - BZOJ5074


题意概括

  BZOJ5074 小B的数字 BZOJ2017年10月月赛 其他


题解

  作为蒟蒻的我第一个就选择了过的人最多的D题。

  不仔细看好吓人。

  然而并不难。

  我们发现都是2的次幂。

  整除只需要保证被除数的指数大于除数就可以了。

  那么我们只考虑指数。对于一个数a[i],这个数最终所占用的指数一定大于等于总指数和的 $\frac 1 {a[i]}$

  那么我们只需要把每一个a[i]的占用率加起来,如果大于1,那么就不行。

  时间复杂度O(Tn)

  (说实话,作为蒟蒻的我是先试了试,过了(滑稽.jpg),然后再思考证明……)


代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int N=100005;
int T,n;
double p;
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
p=0;
for (int i=1,x;i<=n;i++){
scanf("%d",&x);
p=p+1.0/x;
}
puts(p>1?"NO":"YES");
}
return 0;
}

  

上一篇:Spring学习(十八)Bean 的三种依赖注入方式介绍


下一篇:接口与继承:方法覆盖(super)