【前后缀GCD】ABC125 C

小鱼儿 2024-03-17 19:43 114阅读 0赞

[C - GCD on Blackboard (atcoder.jp)][C - GCD on Blackboard _atcoder.jp]

题意：

![fb786948a649458db8fbd59f368d7ff0.png][]

![ceddabf5a6e342ebacb86f8a7c860f0e.png][]

![eedacfcc5cd84c80ad04841569e864c9.png][]

思路：

这道题，多看看样例大概就出来了

由样例可知，换成的数可以是其他N-1个数的gcd，这样对答案的贡献也没有影响

所以直接去枚举换的是什么数就行

因此怎么去快速求其他N-1个数的GCD就成了问题

这样trick非常经典，在牛客寒假营就出现过

它那个是前后缀背包，这个是前后缀GCD

[(144条消息) 【前后缀背包】牛客寒假集训营4 D 清楚姐姐学01背包(Hard Version)\_lamentropetion的博客-CSDN博客][144_ _4 D _01_Hard Version_lamentropetion_-CSDN]

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=2e5+10;
    const int mxv=2e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N;
    int a[mxn];
    int pre[mxn],suf[mxn];
    
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++) cin>>a[i];
        for(int i=1;i<=N;i++) pre[i]=__gcd(pre[i-1],a[i]);
        for(int i=N;i>=1;i--) suf[i]=__gcd(suf[i+1],a[i]);
        int ans=0;
        for(int i=1;i<=N;i++) ans=max(ans,__gcd(pre[i-1],suf[i+1]));
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[C - GCD on Blackboard _atcoder.jp]: https://atcoder.jp/contests/abc125/tasks/abc125_c
[fb786948a649458db8fbd59f368d7ff0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/49b34518646449bdbfc8e3dfc8182f40.png
[ceddabf5a6e342ebacb86f8a7c860f0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/40c123eb5542469280593718c51ee1fc.png
[eedacfcc5cd84c80ad04841569e864c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/fa66bcc2521a41d0a6332a1ebbd8a992.png
[144_ _4 D _01_Hard Version_lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/129179556