题解：P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi

yokai_ing · 2025-02-20 22:35:37 · 题解

P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi

一个区间的 gcd 可以拆成两个区间的 gcd 的 gcd ，即：

所以可以尝试用 st 表维护区间 gcd ，分别算左右两边，这样查询 \gcd(a_l,a_{l+1},...,a_r) 复杂度 O(\log{n}) 。

然后每次分别二分最左能到达哪里和最右能到哪里，显然最优左，右端点求解时互不影响。可以分别求出（即可以一次只求左，另一次只求右），然后合并为答案。

遍历 1 到 n ，每次二分并在其内查询，复杂度 O(nlog^2{n}) ， 4e8 勉强能过吧。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
int g[MAXN][21],n,b[MAXN];
int ansl[MAXN],ansr[MAXN];
int gcd(int x,int y)
{
    return (y==0?x:gcd(y,x%y));
}
void init()
{
    for(int j=1;j<20;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
    int k=b[r-l+1];
    return gcd(g[l][k],g[r-(1<<k)+1][k]);
}
int ask(int x,int b)
{
    int l=1,r=b==1?x-1:n-x,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        int now=(b==1?query(x-mid,x):query(x,x+mid));
        if(g[x][0]==now)
            ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=1e6;i++)
        b[i]=b[i/2]+1;
    for(int i=1;i<=n;i++)
        scanf("%d",&g[i][0]);
    init();
    for(int i=n;i>=1;i--)
        ansl[i]=i-ask(i,1),
        ansr[i]=i+ask(i,2);
    for(int i=1;i<=n;i++)
        printf("%d ",ansr[i]-ansl[i]+1);
    return 0;
}