题解
一个显然的结论： 第二项一定在分母的位置， 其他的都可以在分子。
现在题目只要求判断能否使式子变成一个任意整数， 所以最优情况下让第二项单独当分子。
对$x_2$分解质因数，通过质因数来判断其他数的乘积是否是$x_2$的倍数
时间复杂度$O(sqrt{x} + N)$
代码
1 #include<cstring> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #define rd read() 6 #define rep(i,a,b) for(int i = (a); i <= (b); ++i) 7 #define per(i,a,b) for(int i = (a); i >= (b); --i) 8 using namespace std; 9 10 const int N = 1e4 + 5; 11 12 int pri[105], tot, cnt[105]; 13 int a[N], T, n, flag; 14 15 int read() { 16 int X = 0, p = 1; char c = getchar(); 17 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1; 18 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0'; 19 return X * p; 20 } 21 22 void init(int x) {//对x2分解质因数 23 int t = x; 24 rep(i, 2, sqrt(x)) if(t % i == 0){ 25 pri[++tot] = i; 26 while(t % i == 0) cnt[tot]++, t /= i; 27 if(t == 1) break; 28 } 29 if(t != 1) pri[++tot] = t, cnt[tot] = 1; 30 } 31 32 int main() { 33 T = rd; 34 for(; T; T-- ) { 35 memset(cnt, 0, sizeof(cnt)); 36 tot = 0; 37 flag = 1; 38 n = rd; 39 rep(i, 1, n) a[i] = rd; 40 init(a[2]); 41 rep(i, 1, n) if(i != 2) 42 rep(j, 1, tot) { 43 while(a[i] % pri[j] == 0 && cnt[j]) cnt[j]--, a[i] /= pri[j]; 44 } 45 rep(i, 1, tot) if(cnt[i]) { 46 flag = 0; 47 break; 48 } 49 if(flag) printf("YES "); 50 else printf("NO "); 51 } 52 }