【GCD枚举因子+环上问题】代码源每日一题div1 最大公约数

怼烎@ 2024-03-16 16:40 64阅读 0赞

[最大公约数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![52f69b0183384303a7b816ade4bde214.png][]

思路：

思路上挺好想的

要让GCD(sum1,sum2,sum3,....sumk)最大，惯用套路，令其为K，那就是让K最大

sum1=k1\*K

sum2=k2\*K

....

所以很自然想到了枚举sum的因子

然后就是给序列分段，让尽可能多的段的段和gcd为因子x

这个又是典中典的东西，直接求个前缀和%x就好了，看看mp\[pre\[i\]%x\]的最大值就是最多能分成几段，然后记录答案即可

还有环的条件，我想的是倍增数组之后O(N)枚举区间，但是这样肯定T

事实上都不需要枚举，因为你一段区间和%x为0了，头尾相接%x也一定是0了

所以根本不需要管环

还有一个很显然的点我没有想到：如果一个序列能分成多段，那么自然可以分成更少段，因此答案数组需要求个后缀最大值

Code：

#include <bits/stdc++.h>
    
    #define low(x) (x&(-x))
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    int N,sum=0;
    int a[mxn],pre[mxn],ans[mxn];
    
    void calc(int x){
        int cnt=0;
        map<int,int> mp;
        for(int i=1;i<=N;i++){
            mp[pre[i]%x]++;
            cnt=max(cnt,mp[pre[i]%x]);
        }
        ans[cnt]=max(ans[cnt],x);
    }
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            pre[i]=pre[i-1]+a[i];
        }
        set<int> S;
        for(int i=1;i<=pre[N]/i;i++){
            if(pre[N]%i==0){
                S.insert(i);
                if(i!=pre[N]/i) S.insert(pre[N]/i);
            }
        }
        for(auto it:S) calc(it);
        for(int i=N;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
        for(int i=1;i<=N;i++) cout<<ans[i]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/131
[52f69b0183384303a7b816ade4bde214.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/39dae5ecda2942f2b6ea96e261ab5568.png