题解：AT_abc400_c [ABC400C] 2^a b^2

szh_AK_all · 2025-04-06 08:38:58 · 题解

为什么很多人没写出来这题啊。

考虑枚举 2^a，这个复杂度我们是很可以接受的，那么问题就转换成了我们要求有多少 b 满足 2^a \times b^2\le n，也就是 b^2\le \lfloor \frac{n}{2^a} \rfloor，那么对 \frac{n}{2^a} 开个根号便是 b 的最大取值。但注意到这样计算可能会算重，例如当 a=2,b=12 时，它代表着 2^2\times 12^2=576，而 576 也可以表示为 2^4\times 6^2，还可以表示为 2^6\times 3^2，这提醒我们当 b 为偶数时，我们就可以从 b 中不断提出 2^2 给 a，所以为了避免算重，我们可以倾定 b 是奇数。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int n;
    cin >> n;
    int x = 1, ans = 0;
    while (1) {
        x *= 2;
        int k = n / x;
        if (!k)
            break;
        ans += (int)sqrtl(k) - ((int)sqrtl(k)) / 2;
    }
    cout << ans;
}