首页 > 代码库 > HDU5726 GCD(ST&RMQ)
HDU5726 GCD(ST&RMQ)
题目链接 GCD
先ST倍增预处理,f[i][j]表示从i开始(包含第i个数)的连续2^j个数的最大公约数。
这样就可以在O(1)内询问得到a[l]到a[r]之间的所有数的最大公约数的值。
然后对于每个数a[i],以这个数为开头的所有子序列的最大公约数的不同值不会超过30个。
而且不同的值是满足单调递减的。
那么就可以二分查找然后把对应值的个数塞进map。
时间复杂度O(Nlog(N))
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i,a,b) for(int i(a); i <= (b); ++i) 6 #define LL long long 7 8 const int N = 100000 + 10; 9 const int A = 30 + 1; 10 11 map <int, LL> mp; 12 int a[N]; 13 int T; 14 int n, m; 15 int l, r; 16 int f[N][A]; 17 int gcd(int a, int b){return b? gcd(b, a % b) : a;} 18 19 inline int Solve(int l, int r){ 20 int k = (int)log2((double)(r - l + 1)); 21 return gcd(f[l][k], f[r - (1 << k) + 1][k]); 22 } 23 24 void Work(){ 25 rep(i, 1, n) f[i][0] = a[i]; 26 rep(j, 1, 17) rep(i, 1, n) if ((i + (1 << j) - 1) <= n) f[i][j] =gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); 27 } 28 29 void setTable(){ 30 mp.clear(); 31 rep(i, 1, n){ 32 int g = f[i][0], j = i; 33 while (j <= n){ 34 int l = j, r = n; 35 while (l < r){ 36 int mid = (l + r + 1) >> 1; 37 if (Solve(l, mid) == g) l = mid; else r = mid - 1; 38 } 39 mp[g] += l - j + 1; 40 j = l + 1; 41 g = Solve(i, j); 42 } 43 } 44 } 45 int main(){ 46 47 scanf("%d", &T); 48 rep(Case, 1, T){ 49 printf("Case #%d:\n", Case); 50 scanf("%d", &n); 51 rep(i, 1, n) scanf("%d", a + i); 52 Work(); 53 setTable(); 54 scanf("%d", &m); 55 while (m--){ 56 scanf("%d%d", &l, &r); 57 int g = Solve(l, r); 58 printf("%d %lld\n", g, mp[g]); 59 } 60 } 61 62 return 0; 63 64 }
HDU5726 GCD(ST&RMQ)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。