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

前言

简要问题重述

解题思路

1. 枚举 ：对于每一个可能的 $a$ ，计算对应的 $b$ 的最大可能值，然后统计满足条件的 b 的个数。
   • 通过 $X = 2^a \times b^2$ 可以解出 $b \leq \sqrt{\frac{N}{2^a}}$ 。
   • $b$ 必须是正整数，因此 $b$ 的最大值是 $\left\lfloor \sqrt{\frac{N}{2^a}} \right\rfloor$ 。
2. 避免重复计数：注意到 $b$ 可以是任意正整数，但不同的 $(a, b)$ 对可能导致相同的 $X$ 。例如 $a = 1, b = 2 和 a = 3, b = 1$ 都得到 $X = 8$ 。
   • 为了避免重复计数，我们需要确保每个 $X$ 只被计数一次。可以通过限制 $b$ 为奇数来实现这一点。
   • 那么为何呢？因为如果 $b$ 是偶数，比如 $b = 2k$ ，那么 $X = 2^a \times (2k)^2 = 2^{a+2} \times k^2$ ，这可以表示为另一个 $a' = a + 2$ 和 $b' = k$ 的形式。因此，只统计 $b$ 为奇数的情况可以避免重复。
3. 统计 b 为奇数的个数：对于固定的 $a ， b$ 的最大值是 $s = \left\lfloor \sqrt{\frac{N}{2^a}} \right\rfloor$ 。奇数 $b$ 的个数是 $\left\lfloor \frac{s + 1}{2} \right\rfloor$ 。

代码

#include<bits/stdc++.h>
using namespace std;
long long i(long long K) {
    long long s = sqrtl(K);
    while (s * s > K) {
        s--;
    }
    while ((s + 1) * (s + 1) <= K) {
        s++;
    }
    return s;
}
int main() {
    long long N;
    cin >> N;
    long long ans = 0;
    for (int a = 1; ; a++) {
        long long power = 1LL << a;
        if (power > N) {
            break;
        }
        long long K = N / power;
        if (K == 0) {
            break;
        }
        long long s = i(K);
        long long count = (s + 1) / 2;
        ans += count;
    }
    cout << ans << endl;
    return 0;
}

后言