CF1485C Floor and Mod 题解

User-Unauthorized / 2023-08-23 / 原文

题面

给定 \(x, y\)，求

\[\sum\limits_{a = 1}^{x} \sum\limits_{b = 1}^{y} \left[\left\lfloor\dfrac{a}{b}\right\rfloor = a \bmod b\right] \]

（\(1 \le x, y \le 10^9, 1 \le T \le 100\)）。

题解

考虑钦定 \(\left\lfloor\dfrac{a}{b}\right\rfloor = a \bmod b = k\)，那么有

\[b \cdot k + k = a \Leftrightarrow b + 1 = \dfrac{a}{k} \]

因为有 \(k = a \bmod b\)，所以 \(k < b\)，结合上式，可得

\[k < \dfrac{a}{k} - 1 \Leftrightarrow k \left(k + 1\right) = a \]

所以 \(k\) 的取值是 \(\sqrt{x}\) 级别的，考虑枚举 \(k\) 的值并计算符合 \(\left\lfloor\dfrac{a}{b}\right\rfloor = a \bmod b = k\) 的数对 \(\left(a, b\right)\) 个数。

首先根据上文等式可得 \(b = \dfrac{a}{k} - 1\)，该条件对 \(b\) 的限制为 \(b \in \left[1, \left\lfloor\dfrac{x}{k}\right\rfloor\right)\)。再考虑到有 \(k < b \Rightarrow b > k\)，综上可得 \(b\) 的取值范围为 \(\left(k, \left\lfloor\dfrac{x}{k}\right\rfloor\right) \cap \left[1,Y\right]\)，\(\mathcal{O}(1)\) 计算即可。总复杂度为 \(\mathcal{O}(T \sqrt{x})\)，可以通过本题。

Code

//Codeforces - 1485C
#include <bits/stdc++.h>

typedef long long valueType;

int main() {
    valueType T;

    std::cin >> T;

    for (valueType testcase = 0; testcase < T; ++testcase) {
        valueType X, Y;

        std::cin >> X >> Y;

        valueType ans = 0;

        for (valueType i = 1; i * (i + 1) < X && i < Y; ++i) {
            ans += std::min(X / i - 1, Y) - i;
        }

        std::cout << ans << '\n';
    }

    std::cout << std::flush;

    return 0;
}