CF1485C Floor and Mod

Autream · 2025-07-15 16:57:32 · 题解

题意简述

对于所有 a \in [1, x], b\in[1, y] 求 \lfloor \frac{a}{b} \rfloor = a \operatorname{mod} b 的数对 (a, b) 的个数。

题目分析

评蓝高了，CF 上都只有 1700。

使用瞪眼法容易发现以下几个性质：

3. 对于任意合法的 b 取值，满足条件的 (a, b) 最多只有 b - 1 个（除 0 以外，b 的余数只有 b - 1 个）。

根据以上性质容易发现，能把一个 b 的所有数对都取完的条件是 \frac{x}{b} \ge b，即 b \le \sqrt x。

对于剩下的 b \in (\sqrt x, y]，此时 \frac{x}{b} < b，它们对答案的贡献即为 x 整除它们的商。

考虑枚举这个商。由于是整除，所以自然想到整除分块。

具体地，对于枚举的 i \in [1, \lfloor \frac{x}{\sqrt x} \rfloor)，商均为 i 的数即为 (\lfloor \frac{x}{i + 1} \rfloor, \lfloor \frac{x}{i} \rfloor] 中的数（根据 y 调整上界），贡献显然。

时间复杂度 O(\sqrt V)。

代码

CI N = 2e5 + 5;
int T, x, y, ans;
signed main() {
    T =  read();
    while(T --) {
        x = read(), y = std::min(x, read()), ans = 0;
        rep(i, 2, std::min(y, (int)std::sqrt(x))) ans += i - 1;
        dep(i, x / (int)std::sqrt(x) - 1, 1) if(x / i ^ x / (i + 1)) {
            if(x / (i + 1) >= y) break;
            ans += i * (std::min(y, x / i) - x / (i + 1)) - (y >= x / i);
        }
        printl(ans);
    }
    return 0;
}