欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ5074
题意概括
题解
作为蒟蒻的我第一个就选择了过的人最多的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;
}