CF1780E Josuke and Complete Graph

MSqwq · 2023-01-26 00:53:34 · 题解

虽然这题出没有啥水平，但是可以复习整除分块，所以写了一下。
首先你看到 l 的范围非常不正常，然后还是多测，不难推测到这题要么预处理，要么每次询问复杂度很低，首先对于前者预处理 10^{18}，肯定不可能所以考虑后者，然后大差不差你猜到了整除分块（数论分块）。
但是没有出现 \lfloor \frac{n}{i} \rfloor 的东西，那怎么思考呢。首先把整个问题分为两类，一类是 \gcd < l ，另一类是 l\le \gcd \le r，对于后面很显然总数是 \lfloor \frac{r}{2} \rfloor-(l-1)，因为你要满足这个数落在区间内，并且这个数的两倍以上也要在这个区间内。
对于第一类，可以考虑整除分块，你整除分块得到的是 \lfloor \frac{n}{i} \rfloor 的东西，那么是不是相当于在这某一块内每个数都满足乘上这个数就是小于 l 且最接近 l 的数，那么设 \lfloor \frac{n}{i} \rfloor 为 k 只要满足这个数乘上 k+1 和 k+2 都落在 l 到 r 内是不是就可以了，那么每一块满足的个数就可以算了，复杂度是 O(T\sqrt l)。
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
const int INF=0x3f3f3f3f;

inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0',c=getchar();}
    return x*f;
}

void solve()
{
    ll l=read(),r=read();
    ll ans=0,n=l-1;
    for(ll L=1,R;L<=n;L=R+1)
    {
        R=n/(n/L);
        ans+=max(0ll,min(R,r/(n/L+2))-L+1);
    }
    cout<<ans+max(0ll,r/2-n)<<endl;
}

int main()
{
    int T=read();
    while(T--)solve();
    return 0;
}