bzoj4052 [CERC2013]Magical GCD
给定一个长为 (n) 的序列,求一个子序列使得子序列的公约数与长度的乘积最大,求这个最大值。共 (T) 组数据。
(nleq10^5, a_ileq10^{12})
gcd,ST表
gym100299 C UVA1642 Magical GCD
固定左端点 (l) ,显然以 (l) 开头的前缀 (gcd) 单调递减,且能够分为不超过 (log a_i) 段相同的值,因为 (gcd) 的每次变化都至少会导致 (gcd) 值除以二
于是考虑用这 (log a_i) 段值更新答案,快速求出每段右端点,计入贡献。可以采用二分,求区间 (gcd) 可以用ST表维护,可以做到 (O(nlog nlog a_i)-O(log a_i))
时间复杂度 (O(nlog nlog a_i^2))
虽然看上去很慢,但上界很松,效率还行……正解放鸽子(逃
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll val[18][maxn];
int Tests, n, lg[maxn];
inline ll gcd(ll a, ll b) {
while (b) {
ll t = a;
a = b, b = t % b;
}
return a;
}
inline ll query(int l, int r) {
int k = lg[r - l + 1];
return gcd(val[k][l], val[k][r - (1 << k) + 1]);
}
inline void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &val[0][i]);
}
for (int i = 2; i <= n; i++) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i < 18; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
val[i][j] = gcd(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]);
}
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (i > 1 && val[0][i - 1] % val[0][i] == 0) {
continue;
}
for (int l = i, r; l <= n; l = r + 1) {
ll k = query(i, l);
r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
query(i, mid) < k ? r = mid - 1 : l = mid;
}
ans = max(ans, k * (l - i + 1));
}
}
printf("%lld
", ans);
}
int main() {
scanf("%d", &Tests);
while (Tests--) {
solve();
}
return 0;
}