题解：P14221 [ICPC 2024 Kunming I] 学而时习之

· · 题解

P14221 题解

很好一道题，使我九遍才过。

题目思路

我们发现如果把一段序列的 \gcd 再扩展一个数，那么新的 \gcd 要么不变，要么变小，且一定是之前 \gcd 的因数。我们不妨设序列的值域为 0 \sim V，那么 \gcd 最多减小 \log V 次，而最坏的情况就是每次 \gcd 减小都是减半，因为除以 2 是减小最慢的情况，此时 \gcd 减小 \log V 次。

我们依据上面一段推出的性质，发现如果固定一个端点（这里我固定右端点），那么影响答案的因素只剩下一段前缀 \gcd（最多有 \log V 种取值）和中间一段加法区间。对于中间一段，我们可以用 ST 表快速维护，而我们贪心地发现，在左边一段答案不变的情况下，中间一段变长不会使答案增加，所以只取每段前缀 \gcd 相等区间的右端点作为前缀 \gcd 的计算，此时中间一段长度最小，可以达到最优答案。

注意一下可以不进行加法操作，也就是直接取一段前缀 \gcd 和一段后缀 \gcd。

题目代码

long long gcd(long long a , long long b)
{
    return (b == 0 ? a : gcd(b , a % b));
}
int t;
long long n , k;
long long qzhgcd[300005] , hzhgcd[300005]; // 前缀 gcd / 后缀 gcd
long long st[300005][20]; // ST 表维护中间一段区间
long long stgcd(int l , int r) // 查询 l ~ r 区间做加法操作的 gcd
{
    int d = log2(r - l + 1);
    return gcd(st[l][d] , st[r - (1 << d) + 1][d]);
}
long long calc(int l , int r) // 计算左边是 1 ~ l，右边是 r ~ n 时的答案
{
    long long ans = 0;
    if(l != 0) // 注意判断边界情况
    {
        ans = (ans == 0 ? qzhgcd[l] : gcd(ans , qzhgcd[l]));
    }
    if(r != n + 1)
    {
        ans = (ans == 0 ? hzhgcd[r] : gcd(ans , hzhgcd[r]));
    }
    if(l + 1 <= r - 1)
    {
        ans = (ans == 0 ? stgcd(l + 1 , r - 1) : gcd(ans , stgcd(l + 1 , r - 1)));
    }
    return ans;
}
void solve()
{
    read(n , k);
    for(int i = 1 ; i <= n ; i++) // 初始化 + 处理
    {
        long long a;
        read(a);
        qzhgcd[i] = a , hzhgcd[i] = a;
        st[i][0] = a + k;
    }
    for(int i = 2 ; i <= n ; i++)
    {
        qzhgcd[i] = gcd(qzhgcd[i - 1] , qzhgcd[i]);
    }
    for(int i = n - 1 ; i >= 1 ; i--)
    {
        hzhgcd[i] = gcd(hzhgcd[i + 1] , hzhgcd[i]);
    }
    for(int i = 1 ; i <= 19 ; i++)
    {
        for(int j = 1 ; j + (1 << i) - 1 <= n ; j++)
        {
            st[j][i] = gcd(st[j][i - 1] , st[j + (1 << i - 1)][i - 1]); // 这里左移的括号加不加都一样
        }
    }
    vector < int > dif; // 记录前缀 gcd 相同区间的右端点
    dif.push_back(0); // 左边一段可以不取
    for(int i = 1 ; i <= n ; i++)
    {
        if(qzhgcd[i] != qzhgcd[i + 1])
        {
            dif.push_back(i);
        }
    }
    long long ans = qzhgcd[n];
    for(int i = n + 1 ; i >= 1 ; i--) // 右边一段可以不取
    {
        ans = max(ans , calc(i , i)); // 中间一段可以不取
        for(int j = 0 ; j < dif.size() ; j++)
        {
            if(dif[j] > i) // 这个判断保证 calc() 函数的前缀 gcd 与后缀 gcd 不会统计重复区间
            {
                break;
            }
            ans = max(ans , calc(dif[j] , i));
        }
    }
    printnl(ans);
    for(int i = 1 ; i <= n ; i++) // 清空数组
    {
        qzhgcd[i] = hzhgcd[i] = 0;
        for(int j = 0 ; j <= 19 ; j++)
        {
            st[i][j] = 0;
        }
    }
}
signed main()
{
    read(t);
    while(t--)
    {
        solve();
    }
    return 0;
}