CF1485C Floor and Mod 题解

题目链接：CF1485C Floor and Mod

题意：

多组询问。给定 $x,y$ ，求 $1\le a\le x,1\le b\le y$ 且 $\lfloor\frac{a}{b}\rfloor =a\bmod b$ 的$(a,b)$ 个数。

数据范围：

$1\le Q \le 100,~1 \leq x, y \leq 10^9$ 。

这道题有点麻烦 QAQ

先推一波柿子

$$\begin{aligned} \left\lfloor{\frac{a}{b}}\right\rfloor &= a \bmod b \\\\\left\lfloor{\frac{a}{b}}\right\rfloor &= a-\left\lfloor{\frac{a}{b}}\right\rfloor\times b \\\\\left\lfloor{\frac{a}{b}}\right\rfloor &=\frac{a}{b+1} \end{aligned}$$

显然 $b +1 \mid a$ ，同时因为 $a \bmod b <b$

所以 $\dfrac{a}{b+1} < b \Rightarrow a<b^2 + b \Rightarrow a \in [0,b^2+b-1]$

则满足条件的 $a$ 的个数为 $\left\lfloor\dfrac{\min\{x,b^2+b-1\}}{b+1}\right\rfloor$

答案就是

$$\sum_{b=1}^{y}\left\lfloor\dfrac{\min\{x,b^2+b-1\}}{b+1}\right\rfloor$$

但是这个东西好像不好用数论分块

仔细观察，当 $b \ge \sqrt{x}-\epsilon,\epsilon\in \mathbb{N}$ 时，柿子是这样的

$$\sum_{b=1}^{y}\left\lfloor\dfrac{x}{b+1}\right\rfloor$$

其实写成 $\sum\limits_{b=2}^{y+1}\left\lfloor\dfrac{x} {b}\right\rfloor$ 可以更明显地看出这是个数论分块的板子

对于 $b < \sqrt{x}-\epsilon,\epsilon\in \mathbb{N}$ 的情况，直接暴力枚举即好了

时间复杂度 $O(Q \sqrt{x})$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q,a,b,x,y,res;
    cin >> Q;
    while(Q--)
    {
        cin >> x >> y;
        a=1,b=1,res=0;
        for(; b*b+b-1<x&&b<=y; b++)
            res+=(b*b+b-1)/(b+1);
        for(int l=b+1,r; l<=min(x,y+1); l=r+1)
        {
            r=min(x/(x/l),y+1);
            res+=x/l*(r-l+1);
        }
        cout << res << '\n';
    }
    return 0;
}