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;
}