trick的来源
有一道题目是这样的:
对于一个由正整数组成的序列,Magical GCD 是指一个区间的长度乘以该区间内所有数字的最大公约数。给你一个序列,求出这个序列最大的 Magical GCD。
(nleq 10^5,a_i leq 10^{12})
暴力的做法是:从左往右枚举右端点(r),再从(r)开始从大到小枚举左端点(l),同时记录([l,r])的(gcd),更新答案
这个暴力显然是(O(n^2))的,考虑优化这个暴力。
用到有一个极其有用的性质:
固定一个右端点(r),那么设(g[l]=gcd(a_l,a_{l+1},a_{l+2},...,a_r)),所有(1leq lleq r)的(g[l])最多只有(logV)种取值,且相同的(g[l])是连续的,(V)是值域。
性质的证明是非常简单的,固定右端点(r)后,我们从(r)开始从大到小枚举(l),那么(g[l])要么不变,要么变小,变小的话至少是除以(2),因此经过(logV)次变小就变成了(1),后面就都是(1)了。
根据这个性质的优化:
建立一个双向链表,一开始(i)的前驱是(i-1),后继是(i+1)。还是从左往右枚举(r),但是这次从左往右沿着双向链表枚举(l),更新(g[l])(就是
g[l]=gcd(g[l],a[r])
)。如果(g[l]=g[pre[l]]),那么我们就从双向链表中删掉(l)。这样做就能保证任何时候(g[l])和(g[nxt[l]])是不同的,只要沿着双向链表枚举就能找到所有(g[l])相同的那(logV)段。
结合代码理解:
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int N = 100007;
typedef long long ll;
int T, n;
ll a[N], g[N];
int nx[N], pr[N];
ll gcd(ll x, ll y)
{
return y ? gcd(y, x % y) : x;
}
void init()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) nx[i] = i + 1, pr[i] = i - 1, g[i] = a[i];
}
void solve()
{
ll ans = 0;
for (int r = 1; r <= n; r++)
for (int l = 1; l <= r; l = nx[l])
{
g[l] = gcd(g[l], a[r]);
if (g[l] * (r - l + 1) > ans)
ans = g[l] * (r - l + 1);
if (g[l] == g[pr[l]])
{
nx[pr[l]] = nx[l];
pr[nx[l]] = pr[l];
}
}
printf("%lld
", ans);
}
int main()
{
scanf("%d", &T);
while (T--) init(), solve();
return 0;
}