题解：P14199 [ICPC 2024 Hangzhou R] Make It Divisible

· · 题解

一句话题解：建出来笛卡尔树，区间限制转变为父子限制。发现合法的 x 不多，枚举判断即可。

首先发现 a_d 必定是区间最小值。考虑建出笛卡尔树，设 fa_p 是节点 p 在笛卡尔树上的父亲节点，则一个 x 合法当且仅当 \forall p,(a_{fa_p}+x)|(a_p+x)。

又有 (a_{fa_p}+x)|(a_p+x)\Leftrightarrow(a_{fa_p}+x)|(a_p-a_{fa_p})。因为 a_p-a_{fa_p} 的因数在 V=10^9 的时候只有 1344 个，所以可以直接枚举所有的 x 并判断是否合法。

接下来证明为什么区间上的限制可以转化为笛卡尔树上父子之间的限制。

显然所有不满足该限制的 x 均不合法，故只需要证明所有的 x 都满足该限制。发现整除关系可以传递，则笛卡尔树上一个节点能整除以它为根的所有节点。对于一个区间，找到区间最小值在笛卡尔树上的对应节点，这个节点的子树肯定包含该区间。故满足该性质的 x 必然合法。

放个代码。

// Problem: P14199 [ICPC 2024 Hangzhou R] Make It Divisible
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14199
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define retunr return
bool startmb;
constexpr int N=5e4+5;
int _,n,k,a[N];

pair<int,int> st[18][N];
pair<int,int> ask(int l,int r){if(l>r) return {0,0};int k=log2(r-l+1);return min(st[k][l],st[k][r-(1<<k)+1]);}

vector<int> vec;
int solve(int l,int r)
{
    if(l>r) return 0;
    int p=ask(l,r).second,ls=solve(l,p-1),rs=solve(p+1,r);
    vector<int> can;
    for(auto x:vec)
    {
        if(ls){if((a[ls]+x)%(a[p]+x)!=0) continue;}
        if(rs){if((a[rs]+x)%(a[p]+x)!=0) continue;}
        can.push_back(x);
    }
    vec.swap(can);
    return p;
}

bool endmb;
main()
{
    cerr<<((&startmb-&endmb)/1024.0/1024)<<endl;
    cin.tie(0)->sync_with_stdio(false);
    int cyc;
    cin>>_,cyc=_;
    for(int i=1;i<=_;i++)
    {
        cin>>n>>k;
        int maxn=LLONG_MIN,minn=LLONG_MAX;
        for(int i=1;i<=n;i++) cin>>a[i],maxn=max(maxn,a[i]),minn=min(minn,a[i]);
        if(maxn==minn) {cout<<k<<' '<<k*(k+1)/2<<'\n';continue;}
        for(int i=1;i<=n;i++) st[0][i]={a[i],i};
        for(int i=1;i<=17;i++) for(int j=1;j+(1<<(i-1))<=n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
        for(int i=1;i<n;i++)
        {
            if(a[i]!=a[i+1])
            {
                int x=min(a[i],a[i+1]),y=max(a[i],a[i+1]),val=abs(a[i+1]-a[i]);
                for(int t=1;t*t<=val;t++)
                {
                    if(val%t==0)
                    {
                        if(1<=t-x&&t-x<=k) vec.push_back(t-x);
                        if(t*t!=val&&1<=val/t-x&&val/t-x<=k) vec.push_back(val/t-x);
                    }
                }
                break;
            }
        }
        solve(1,n);
        int ans=0;
        for(auto x:vec) ans+=x;
        cout<<vec.size()<<' '<<ans<<'\n';
        vec.clear();
    }
    return 0;
}