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

思路：

根据题意，需要尝试所有可能的区间

(l , r)

，将该区间内的元素都加

k

后，计算整个序列的最大公因数。

但是但是，如果直接模拟处理，时间肯定就炸飞了。

为了高效计算，可以预处理两个辅助数组：

pre\_gcd_i

：表示前

i

个元素的最大公因数。

last\_gcd_i

：表示从

i

到

n

所有元素的最大公因数。

然后遍历每个可能的区间起点

i

，若前缀最大公因数无变化则跳过。

从

i

开始扩展区间终点

j

，计算区间

(i , j)

中的数加

k

后的最大公因数（记为

s

）。

结合

s

与区间右侧的后缀最大公因数，得到整个序列的最大公因数，并更新答案。

完结撒花~

Code

CPP

#include<bits/stdc++.h>
using namespace std ;
const int maxn=3e5+5;
int n;
long long k,a[maxn],last_gcd[maxn],pre_gcd[maxn],s;
long long ans=0;
long long gcd (long long a, long long last_gcd) { 
	if (last_gcd==0) return a;
	if (a%last_gcd==0) return last_gcd;
	return gcd(last_gcd,a%last_gcd);
}
int main () {
    int t;
    cin>>t;
    while (t--) {
        cin>>n>>k;
        for (int i=1;i<=n;i++) cin>>a[i];
        for (int i=1;i<=n;i++) pre_gcd[i]=gcd(pre_gcd[i-1],a[i]);
        last_gcd[n+1]=0;
        for(int i=n;i>=1;i--) last_gcd[i]=gcd(last_gcd[i+1],a[i]);
        ans=pre_gcd[n];
        for (int i=1;i<=n;i++) {
            if (pre_gcd[i]==pre_gcd[i-1]) continue;
            s=pre_gcd[i-1];
            for (int j=i;j<=n;j++) {
                s=gcd(s,a[j]+k);
                ans =max(ans,gcd(s,last_gcd[j+1]));
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

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

文章操作

思路：

相关推荐

评论

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