题面
给定 \(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, \dfrac{x}{k}\right)\)。再考虑到有 \(k < b \Rightarrow b > k\)，综上可得 \(b\) 的取值范围为 \(\left(k, \dfrac{x}{k}\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;
}