CF1996D 题解

Manki23333333 · 2024-07-27 07:50:36 · 题解

由于 Rating 非常低，来打 div3 了。

题意

给定 n, k，求满足 a+b+c \le x 且 ab+ac+bc \le n 的三元组 (a, b, c) 个数。

题解

考虑暴力枚举。复杂度 O (n^3) ，很显然会爆炸掉。

但是我们发现，它有一个单调性。当我们固定了 a ,b，枚举 t 是一个合法的 c 时，我们发现，t - 1 一定也合法。如果 t 不合法，那么 t + 1 照样不合法。所以我们可以通过数学方法算 c 的最大值，方案就加上这个最大值。

但是我们优化了一个 O (n)，还是有 O (n^2)，照样会 T 飞。但是很显然，我们并不用 O (n) 来枚举 b。因为必须满足 ab < n，这样的复杂度是 O (\log n) 的。

证明

枚举 b 的复杂度为 O (\frac {n} {1} + \frac {n} {2} +\frac {n} {3} + ......)。这是 n 项的调和级数。中间的式子其实等价于 nH_n，其中定义 H_x=\frac {1} {1}+\frac {1} {2}+\frac {1} {3}+\frac {1} {4}+......+\frac {1} {x}。我们又知道， \log x 实际上近似于 H_x，两者相差一个欧拉常数和一个小常数，且这个常数在 \lim\limits_{x\to 0}时为 0，误差可以忽略不计。

代码

#include <bits/stdc++.h>

using namespace std;

int n, x;

void solve () {
    cin >> n >> x;

    int ans = 0;
    for (int a = 1 ; a <= x ; a ++) {
        for (int b = 1 ; b <= x && a * b <= n ; b ++) {
            if (a * b >= n || (a + b) >= x || (n - a * b) < (a + b))
                continue;

            ans += min (x - a - b, (n - a * b) / (a + b));
        }
    }

    cout << ans << endl;
}

int main () {
    int T;

    cin >> T;

    while (T --) {
        solve ();
    }
    return 0;
}