CF1485C Floor and Mod

· · 题解

整套题目全部题解链接：Codeforces Round #701 (Div. 2) A ~ F ，6题全，超高质量良心题解【每日亿题】2021/2/13

C - Floor and Mod

Problem C Floor and Mod

Translation

定义一对数 (a,b) 是特殊的，当且仅当 \lfloor\dfrac{a}{b}\rfloor=a\bmod b

给定 x 和 y ，求一共有多少对特殊的数 (a,b) ，当 1\le a\le x,1\le b\le y。

Solution

签到题

看数据范围，显然这是一个结论题或者 O(\sqrt n) 枚举题，我们根据题目中给定的柿子：

\lfloor\dfrac{a}{b}\rfloor=a-\lfloor\dfrac{a}{b}\rfloor\times b&\\& a=\lfloor\dfrac{a}{b}\rfloor\times (b+1)&\\& \dfrac{a}{b+1}=\lfloor\dfrac{a}{b}\rfloor\end{aligned}

因为\lfloor\dfrac{a}{b}\rfloor 一定是整数，所以 \dfrac{a}{b+1} 一定是整数，所以 b+1\ |\ a。

所以一个很直观的想法就是枚举 b ，对于每一个 b ， b+1 的倍数 a 显然有 \dfrac{x}{b+1} 个，显然可以整除分块。

但是需要注意题目中的给定的条件为 \lfloor\dfrac{a}{b}\rfloor=a\bmod b

即： \lfloor\dfrac{a}{b}\rfloor<b

即：\dfrac{a}{b+1}<b\Rightarrow a<b^2+b

即 a\in [0,b^2+b-1]。那么符合题意的 a 的个数就是： \dfrac { b^2+b-1}{b+1}

并且 a 的上限是 x，故最终的答案为：

\sum\limits_{b=1}^{y} ans = \dfrac {\min \{x, b^2+b-1\}}{b+1}

我们可以先枚举 b<\sqrt x ，计算 \dfrac { b^2+b-1}{b+1}

剩余的 b=\sqrt x \sim y，显然 {\min\{x, b^2+b-1\}}=x，直接整除分块即可，其中整除分块的时候，我们需要计算的是 \lfloor \dfrac{x}{b+1}\rfloor，我们令 l,r 代表 b+1 即可。

时间复杂度 O(\sqrt x)

Code

// Problem: C. Floor and Mod
// Contest: Codeforces - Codeforces Round #701 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1485/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1e5 + 7;

int n, m, t;
int x, y;

int main()
{
    scanf("%d", &t);
    while(t -- ) {
        scanf("%d%d", &x, &y);
        int a = 1, b = 1;
        ll ans = 0;
        for(; b * b + b - 1 < x && b <= y; ++ b) 
            ans += (b * b + b - 1) / (b + 1);      

        int l = b + 1, r;  
        for(; l <= x && l <= y + 1; l = r + 1) {
            r = min(x / (x / l), y + 1);
            ans += x / l * (r - l + 1); 
            if(r == y + 1) break;
        } 
        cout << ans << endl;
    }       
    return 0;
}