题解 CF1996D Fun
Luogu Link | Codeforces Link
\(\texttt{Describe}\)
给定两个整数 \(n,x\)，求满足 \(ab+bc+ac \le n\) 且 \(a+b+c\le x\) 的正整数三元组 \((a,b,c)\) 的个数。
\(\texttt{Solution}\)
首先考虑暴力：枚举 \(a,b\)，可推出 \(c\) 的取值范围：
-
对于 \(ab+bc+ac \le n\)，我们稍微变形：\((a+b)c \le n - a \times b\)，左右除 \((a+b)\)：\(c \le \frac{n-a \times b}{a+b}\)。
-
对于 \(a+b+c \le x\)，变形得：\(c \le x - a - b\)。
根据不等式的性质（同大取大，同小取小）：\(1 \le c \le \min(x-a-b,\frac{n-a \times b}{a+b})\)。
算下复杂度发现：\(b \le \min(x-a,\frac{n}{a})\)，是能过的。
\(\texttt{Code}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, x;
void solve() {
ll ans = 0;
cin >> n >> x;
for (int a = 1; a <= x; ++a) {
for (int b = 1; a + b <= x && 1ll * a * b <= n; ++b) {
ans += min(x - a - b, (n - a * b) / (a + b));
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T; while (T --) solve();
return 0;
}