Description

询问 \(1 \leq a \leq x\) ，\(1\leq b \leq y\) ，且满足 \(\lfloor \frac{a}{b}\rfloor =a\bmod b\) 的有序对 \((a,b)\) 有多少对。

Sol

先用 \(b\) 把 \(a\) 表示出来，有

\[a=b\times\lfloor \frac{a}{b}\rfloor + a\bmod b \]

记 \(\lfloor \frac{a}{b}\rfloor=a\bmod b=c\)，则

\[a=(b+1)c \]

那么，如果 \(b\) 是确定的，一个 \(c\) 就唯一对应了一个 \(a\) 。而这样的 \(c\) 有 \(\lfloor \frac{x}{b+1} \rfloor\) 个。还注意到一点，由于 \(c\) 是余数，所以 \(c\) 一定要小于 \(b\) 。
那么答案即为

\[\sum_{i=1}^y \min(i-1,\lfloor \frac{x}{i+1} \rfloor) \]

此时已经有了一个 \(O(y)\) 的算法，但这显然不够。为了化简这个和式，首先想到的是把 \(min\) 去掉。容易发现 \(i-1\) 单增，\(\lfloor \frac{x}{i+1} \rfloor\) 单减，所以可以直接二分找函数交点，分成两段单独求和。
前面的一段可以直接等差数列求和，而后面的一段直接整数分块即可，复杂度 \(O(\log n+\sqrt{n})=O(\sqrt{n})\)

#include<stdio.h>
#define ll long long

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

int T;
ll x,y;

inline int min(int x,int y){return x<y? x:y;}

int main(){
    T=read();
    while(T--){
        x=read(),y=read();
        ll ans=0;
//        for(int i=1;i<=y;i++)
//            ans+=min(i-1,x/(i+1));
        int l=1,r=y,ret=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(mid-1<=x/(mid+1)) l=mid+1,ret=mid;
            else r=mid-1;
        }
        ans=(1ll*ret*(ret-1))>>1;
        for(l=ret+2,r=0;l<=min(x,y+1);l=r+1){
            r=min(y+1,x/(x/l));
            ans+=(r-l+1)*(x/l);
        }
        printf("%lld\n",ans);
    }
}

Tips

要注意一下整数分块的边界，是 \(y+1\) 而不是 \(y\)。又由于是在对 \(x\) 整数分块，但边界取的是 \(y\) ，所以算 \(r\) 的时候要注意和 \(y+1\) 取 \(min\)。（在这个地方卡了半天，交的时候这题只剩 1000 分不到了，血亏）