首页 > 其他 > 详细

BZOJ 1385 [Baltic2000] Division expression

时间:2018-08-19 20:50:07      阅读:169      评论:0      收藏:0      [点我收藏+]

题解

一个显然的结论: 第二项一定在分母的位置, 其他的都可以在分子。

现在题目只要求判断能否使式子变成一个任意整数, 所以最优情况下让第二项单独当分子。

对$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\n");
50         else printf("NO\n");
51     }
52 }
View Code

 

BZOJ 1385 [Baltic2000] Division expression

原文:https://www.cnblogs.com/cychester/p/9502513.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!