题目描述

一个正整数 X 被称为 好整数，当且仅当它满足以下条件：

• 存在一对正整数 (a, b) 使得 X = 2^a * b^2。

例如，400 是一个好整数，因为 400 = 2^2 * 10^2 （这里 a=2, b=10）。
另一个例子，18 = 2^1 * 3^2 （这里 a=1, b=3）。
72 = 2^3 * 3^2 (这里 a=3, b=3)。72 也可以写成 2^1 * 6^2 (这里 a=1, b=6)，只需要存在 至少一对 (a, b) 即可。

给定一个正整数 N，找出在 1 到 N（包含两端）之间有多少个好整数。

样例

输入:
20

输出:
5

说明：在 1 到 20 之间有 5 个好整数：
2 = 2^1 * 1^2 (a=1, b=1)
4 = 2^2 * 1^2 (a=2, b=1)
8 = 2^3 * 1^2 (a=3, b=1)
16 = 2^4 * 1^2 (a=4, b=1)
* 18 = 2^1 * 3^2 (a=1, b=3)

输入:
400

输出:
24

输入:
1234567890

输出:
42413

注意：输入 N 可能很大，需要使用 64 位整数类型。

算法 (枚举 + 数学)

$O(\log N \times \log N)$ 或 $O(\log N)$ 取决于求平方根的复杂度

思路分析

1. 理解好整数的结构:
   一个数 X 是好整数，意味着 X = 2^a * b^2，其中 a >= 1 且 b >= 1。

2. 唯一表示:
   直接统计满足条件的 (a, b) 对可能会重复计算同一个 X。例如 72 = 2^1 * 6^2 = 2^3 * 3^2。我们需要找到一种方法来唯一地表示或生成每一个好整数 X。
   考虑 X 的质因数分解。如果 X 是好整数，X = 2^a * b^2。设 b 的质因数分解为 b = 2^k * m，其中 m 是 b 的奇数部分（k >= 0，m >= 1 且 m 为奇数）。
   那么 X = 2^a * (2^k * m)^2 = 2^a * 2^{2k} * m^2 = 2^{a+2k} * m^2。
   令 A = a + 2k。因为 a >= 1 且 k >= 0，所以 A >= 1。
   令 B = m。因为 b >= 1，所以 m >= 1，且 m 是奇数。
   所以，任何一个好整数 X 都可以表示为 X = 2^A * B^2 的形式，其中 A >= 1，B >= 1 且 B 是 奇数。
   这种表示是唯一的吗？假设 X = 2^A * B^2 = 2^C * D^2，其中 A, C >= 1 且 B, D >= 1 都是奇数。根据算术基本定理（唯一质因数分解），比较等式两边的质因数分解，奇数部分的平方必须相等，即 B^2 = D^2，因为 B, D 都是正数，所以 B = D。同样，2 的幂次也必须相等，即 A = C。
   因此，每个好整数 X 都可以 唯一地 表示为 X = 2^A * B^2，其中 A >= 1，B >= 1 且 B 为奇数。

3. 计数策略:
   我们的目标是计算满足 1 <= X <= N 的好整数 X 的数量。这等价于计算满足以下条件的 唯一 对 (A, B) 的数量：

   • A >= 1
   • B >= 1 且 B 是奇数
   • 2^A * B^2 <= N

4. 迭代变量选择:
   直接计算满足条件的 (A, B) 对仍然有些困难。我们可以尝试固定一个变量，然后计算另一个变量的可能性。

   • 固定 B (奇数): 对于一个固定的奇数 B >= 1，我们需要 2^A <= N / B^2 且 A >= 1。设 K = N / B^2。我们需要 2^A <= K 且 A >= 1。满足条件的 A 的个数是 max(0, floor(log2(K)))。我们需要对所有奇数 B 求和。B 的范围是多少？因为 2^A >= 2^1 = 2，所以 2 * B^2 <= N，即 B^2 <= N/2，B <= sqrt(N/2)。迭代 B 到 sqrt(N) 级别（最高 10^9）还是太慢。
   • 固定 A: 对于一个固定的 A >= 1，我们需要 B^2 <= N / 2^A，B >= 1 且 B 是奇数。设 K = N / 2^A。我们需要 B^2 <= K，B >= 1 且 B 是奇数。
     • 首先，B 的最大可能值是 m = floor(sqrt(K))。
     • 我们需要计算在 [1, m] 这个范围内有多少个奇数 B。
     • 奇数序列是 1, 3, 5, ...。第 k 个奇数是 2k-1。
     • 我们需要 2k-1 <= m，即 2k <= m+1，所以 k <= (m+1)/2。
     • 因此，[1, m] 中奇数的个数是 floor((m+1)/2)。在 C++ 中，使用整数除法 (m + 1) / 2 即可得到这个结果。
     • 我们需要对所有可能的 A 值求和。A 的范围是多少？因为 B^2 >= 1^2 = 1，所以 2^A * 1 <= N，即 2^A <= N。所以 A 的最大值是 floor(log2(N))。
     • 由于 N <= 10^18，log2(N) 大约是 60。所以 A 的取值范围很小，从 1 到 大约 60。
     • 这个方法可行！

5. 算法流程:

   • 初始化总数 sum = 0。
   • 循环变量 A 从 1 开始。
   • 在循环中，计算 pow2 = 2^A。注意使用 64 位整数 (long long) 防止溢出。1LL << A 是计算 2^A 的常用方法。
   • 检查 pow2 是否已经大于 N。或者更稳健地，计算 k = N / pow2（整数除法）。如果 k == 0，说明 2^A > N，对于当前及更大的 A，不可能找到满足条件的 B，可以提前结束循环。
   • 计算 m = floor(sqrt(k))。我们需要一个高效的整数平方根函数。二分查找是标准方法。floor_sqrt(k) 函数实现的就是这个。它找到最大的整数 l 使得 l * l <= k。
   • 计算 [1, m] 范围内的奇数个数：num_odd_b = (m + 1) / 2。
   • 将 num_odd_b 加到 sum 上。
   • 增加 A，继续循环，直到 k 变为 0。
   • 循环结束后，sum 就是答案。

6. 整数平方根 (floor_sqrt):
   函数 floor_sqrt(k) 使用二分查找来计算 floor(sqrt(k))。

   • 设置查找范围 [l, r]，初始为 [0, 1e9 + 1] （因为 k <= N <= 10^18，sqrt(k) <= 10^9，所以 10^9 + 1 是一个安全的上界）。
   • 当 l < r 时，计算中间值 mid = l + (r - l + 1) / 2 （这种写法防止 l+r 溢出，并且倾向于取右中位数，配合 l=mid 更新，避免死循环）。
   • 检查 mid * mid <= k 是否成立。同样需要注意 mid * mid 可能溢出 long long。更安全的方法是检查 mid <= k / mid （需要确保 mid > 0，不过在我们的二分实现中 mid 总是非负，如果 mid=0 不等式也成立）。
   • 如果 mid <= k / mid（即 mid^2 <= k），说明 mid 可能就是答案，或者答案比 mid 更大，所以更新下界 l = mid。
   • 否则（即 mid^2 > k），说明 mid 太大了，更新上界 r = mid - 1。
   • 循环结束时（l == r），l 就是最大的满足 l*l <= k 的整数。

时间复杂度

• 外层循环的次数取决于 A 的范围，最多约为 log2(N) 次，大约 60 次。
• 循环内部的主要操作是计算 pow2（O(1) 位运算），整数除法（O(1)），和整数平方根 floor_sqrt。
• floor_sqrt 使用二分查找，其范围最大是 10^9，所以需要 log(10^9) 大约 30 次迭代。每次迭代是 O(1) 的计算。
• 因此，总时间复杂度大约是 O(log N * log(sqrt(N))) = O((log N)^2)。如果认为 log(sqrt(N)) 相对 log N 是常数级的（因为它们只差一个常数因子 1/2），也可以认为是 O(log N) 次高精度运算。在这个问题规模下，60 * 30 次操作是非常快的。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名

// 计算 floor(sqrt(k))，即小于等于 sqrt(k) 的最大整数
// 使用二分查找实现
i64 floor_sqrt(i64 k) {
    i64 l = 0, r = 1e9 + 1; // 初始化二分查找的左右边界 [l, r]
                           // sqrt(10^18) = 10^9, 所以 10^9 + 1 是安全的上界
    while (l < r) {
        // 计算中间值 mid，倾向于取右中位数，避免 l = mid 时死循环
        i64 mid = l + (r - l + 1) / 2;
        // 检查 mid*mid <= k 是否成立
        // 为了防止 mid*mid 溢出 i64，使用除法判断： mid <= k / mid
        // 需要注意 mid=0 的情况，但这里 mid >= l >= 0，且 mid=0 时 mid <= k/mid 总成立
        if (mid <= k / mid) {
            // 如果 mid*mid <= k，说明 mid 可能是答案，或者答案更大
            // 所以将下界更新为 mid
            l = mid;
        } else {
            // 如果 mid*mid > k，说明 mid 太大了
            // 将上界更新为 mid - 1
            r = mid - 1;
        }
    }
    // 循环结束时 l == r，l 就是 floor(sqrt(k))
    return l;
}

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    i64 n; // 输入 N (可能高达 10^18)
    cin >> n;

    i64 sum = 0; // 用于累计好整数的数量
    // 循环遍历唯一表示 X = 2^A * B^2 中的指数 A
    // A 从 1 开始。A 最大约为 60 (log2(10^18))
    for (int i = 1; i <= 60; i ++ ) { // 循环到 60 足够了
        // 计算 2^A (即 2^i)，使用 1LL 确保是 long long 类型
        i64 pow2 = (1LL << i);

        // 如果 pow2 已经大于 n，或者 n / pow2 < 1 (即 pow2 > n)，则后续的 i 更大，
        // 对应的 B^2 必须小于 1，不可能存在 B >= 1。
        // 所以可以提前结束循环。
        // 计算 k = N / (2^A)
        i64 k = n / pow2;
        if (k == 0) { // 等价于 pow2 > n
            break;
        }

        // 我们需要找到满足 B^2 <= k 且 B 为奇数的 B 的个数
        // 先找到满足 B^2 <= k 的最大 B，即 m = floor(sqrt(k))
        i64 m = floor_sqrt(k);

        // 计算 [1, m] 中有多少个奇数
        // 奇数个数为 floor((m+1)/2)，用整数除法计算 (m + 1) / 2
        i64 num = (m + 1) / 2;

        // 将找到的奇数 B 的个数累加到总数 sum
        sum += num;
    }

    // 输出最终结果
    cout << sum << "\n";

    return 0; // 程序正常结束
}