【GCD可交性】CF731div3 F

落日映苍穹つ 2024-03-27 13:54 82阅读 0赞

**好难不会**

**感觉见过以后应该就会了吧**

[Problem - F - Codeforces][]

题意：

给定一个序列，每次操作可以让一个数与后面那个数取gcd，问你最少操作几次可以使这个序列的所有数变成一样的

思路：

![57382d39efcb6262bcb395f601468cde.png][]

ST表可以维护一个区间的gcd,max,min，因为这些性质都满足可交性

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=2e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    using namespace std;
    
    
    int n,gc;
    int f[mxn<<1][33],lg[mxn];
    void init(){
        lg[1]=0;
        for(int i=2;i<mxn;i++) lg[i]=lg[i>>1]+1;
    }
    int calc(int l,int r){
        int k=lg[r-l+1];
        return __gcd(f[l][k],f[r-(1<<k)+1][k]);
    }
    bool check(int x){
        for(int i=1;i<=n;i++){
            if(calc(i,i+x)!=gc) return false;
        }
        return true;
    }
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>f[i][0],f[i+n][0]=f[i][0];
        gc=f[1][0];
        for(int i=2;i<=n*2;i++) gc=__gcd(gc,f[i][0]);
        for(int j=1;j<=30;j++){
            for(int i=1;i+(1<<(j-1))<=n*2;i++) f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
        int l=0,r=n;
        int ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        //cout<<calc(2,2+3)<<'\n';
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        init();
        while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1547/problem/F
[57382d39efcb6262bcb395f601468cde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/669932b3cd604ee6be26a30ec0ec1971.png