首页 > 代码库 > [BZOJ4052][Cerc2013]Magical GCD
[BZOJ4052][Cerc2013]Magical GCD
[BZOJ4052][Cerc2013]Magical GCD
试题描述
给出一个长度在 100 000 以内的正整数序列,大小不超过 10^12。
求一个连续子序列,使得在所有的连续子序列中,它们的GCD值乘以它们的长度最大。
输入
本题为多组数据。
第一行一个整数 T,表示数据组数。
每组数据第一行为一个整数 n,表示序列长度;第二行为 n 个整数表示序列。
输出
对于每组数据,输出 max{ gcd * length }
输入示例
1 5 30 60 20 20 20
输出示例
80
数据规模及约定
见“试题描述”
题解
可以发现,随着子序列的增长,gcd 要么不变,若变化则变化后的 gcd 不会超过原来的 1/2,所以 gcd 的变化次数不会超过 log21012 = 12 · log210 次。
有了上面的结论,我们就可以枚举左端点,然后向右二分 gcd 即将变化的位置(维护区间 gcd 可以用 ST 表),在每个这样的位置更新答案,然后移动子序列右端点,重复这个过程。设数字大小为 A,那么更新答案次数为 log2A;每次二分需要 log2n;哦对了虽然 RMQ 询问复杂度 O(1),但是每次需要取 gcd,最坏情况 log2A;别忘了我们还枚举了左端点有一个 n,所以最终复杂度不会超过 O(n · log22A · log2n)。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <stack> #include <vector> #include <queue> #include <cstring> #include <string> #include <map> #include <set> using namespace std; #define LL long long const int BufferSize = 1 << 16; char buffer[BufferSize], *Head, *Tail; inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++; } LL read() { LL x = 0, f = 1; char c = Getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); } return x * f; } #define maxn 100010 #define maxlog 17 int n; LL A[maxn]; LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } LL Gcd[maxlog][maxn]; int Log[maxn]; void rmq_init() { Log[1] = 0; for(int i = 2; i <= n; i++) Log[i] = Log[i>>1] + 1; for(int i = 1; i <= n; i++) Gcd[0][i] = A[i]; for(int j = 1; (1 << j) <= n; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++) Gcd[j][i] = gcd(Gcd[j-1][i], Gcd[j-1][i+(1<<j-1)]); return ; } LL query(int l, int r) { int len = r - l + 1, t = Log[len]; return gcd(Gcd[t][l], Gcd[t][r-(1<<t)+1]); } int main() { int T = read(); while(T--) { n = read(); for(int i = 1; i <= n; i++) A[i] = read(); rmq_init(); LL ans = 0; for(int L = 1; L <= n; L++) { int R = L; LL tmp = query(L, R); while(R < n) { int l = R, r = n + 1; while(r - l > 1) { int mid = l + r >> 1; if(query(L, mid) == tmp) l = mid; else r = mid; } R = l; ans = max(ans, tmp * (R - L + 1)); R++; tmp = query(L, R); } if(R <= n) ans = max(ans, tmp * (R - L + 1)); // mark!! } printf("%lld\n", ans); } return 0; }
大视野数据好强!我就因为少加 "mark!!" 那一行导致 WA 了一上午。。。
[BZOJ4052][Cerc2013]Magical GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。