数论分块练习题 | 题解：P13357 [GDCPC 2024] Menji 和 gcd

Vct14 · 2025-07-21 15:22:26 · 题解

刚好最近学了数论分块，来写篇题解。

有一个朴素的思路是暴力枚举因子，判断区间内是否有两个该因子的倍数，即是否有 \left\lfloor\frac{R}{x}\right\rfloor-\left\lfloor\frac{L-1}{x}\right\rfloor\ge2，然后更新答案。但是这样显然超时。

注意到我们判断的是 \left\lfloor\frac{R}{x}\right\rfloor 和 \left\lfloor\frac{L-1}{x}\right\rfloor，考虑使用数论分块，将 \left\lfloor\dfrac nx\right\rfloor 相同的数打包同时计算并更新答案。时间复杂度 O(T\sqrt R)。

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    int t;cin>>t;
    while(t--){
        int L,R;cin>>L>>R;
        int l=1,ans=0;
        while(l<=R){
            int r=min(R/(R/l),(L-1)/l==0?LLONG_MAX:(L-1)/((L-1)/l));
            if(R/l-(L-1)/l>=2) ans=max(ans,r);
            l=r+1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

注意：当 l>(L-1) 时，\left\lfloor\frac{L-1}{l}\right\rfloor=0，则求 \left\lfloor\dfrac{L-1}{\left\lfloor\frac{L-1}{l}\right\rfloor}\right\rfloor 会导致 RE，记得特判。