题目描述
给定数列$a_i$，问是否存在满足下列条件的数列$b_i$：
$b_i=2^p,pin N^*\forall k(prodlimits_{i=1}^nb_i|b_k^{a_k})$
输入
第一行一个正整数T 表示数据组数。
对于每一组数据：
第一行一个正整数n，表示两串数的长度。
第二行n 个用空格隔开的正整数$a_1...a_n$。
输出
对于每一组数据，输出一行“YES”或者“NO”（不含双引号），表示是否可能找到满足题意的$b_1...b_n$。
样例输入
3
2
3 2
3
3 3 3
2
1 10
样例输出
YES
YES
NO
题解
考虑将$b$取$log$，设$w_i=log_2b$，那么原限制条件就变成：
$w_iin N^*\forall k(sumlimits_{i=1}^nw_ile a_kw_k)$
注意到这个限制条件的成立性在所有$w_i$均乘上一个数时不变，因此可以把$w_i$的范围扩展到所有正有理数，因为只需要乘上它们分母的lcm即可变为正整数。
于是有：
$w_i>0\forall k(sumlimits_{i=1}^nw_ile a_kw_k)$
把第二个限制条件变形可以得到：
$forall k(frac{sumlimits_{i=1}^nw_i}{a_k}le w_k)$
因此把不等式加起来可以得到：
$sumlimits_{i=1}^nfrac 1{a_i}·sumlimits_{i=1}^nw_ile sumlimits_{i=1}^nw_i$
由于$w_i$为正，因此它们的和也是正数。所以当且仅当$sumlimits_{i=1}^nfrac 1{a_i}ge 1$时，不等式有解。
因此当不满足此条件时不等式无解，因此也意味着不存在满足条件的$w_i$。
当满足条件$sumlimits_{i=1}^nfrac 1{a_i}ge 1$，可以令$w_i=frac 1{a_i}$，代入易证满足条件，因此存在满足条件的解。
由此得到结论：$sumlimits_{i=1}^nfrac 1{a_i}ge 1$时有解，否则无解。
为了避免浮点数误差，使用$10!$除以$a_i$即可。
时间复杂度$O(Tn)$
#include <cstdio>
#define fac 3628800
int main()
{
int T;
scanf("%d" , &T);
while(T -- )
{
int n , i , x;
long long s = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , s += fac / x;
if(s <= fac) puts("YES");
else puts("NO");
}
return 0;
}