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

· · 题解

前言

一道不错的，难度适中的数论题

简要问题重述

一个正整数 X 被称为“好整数”，当且仅当存在一对正整数 (a, b) 满足 X = 2^a \times b^2 。给定一个正整数 N ，求在 1 到 N 之间（包括 N ）的所有“好整数”的个数。

解题思路

  1. 枚举 ：对于每一个可能的 a ，计算对应的 b 的最大可能值，然后统计满足条件的 b 的个数。
    • 通过 X = 2^a \times b^2 可以解出 b \leq \sqrt{\frac{N}{2^a}} 。
  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 。

代码

复杂度为 O(\log N) ，赛时不知为何调的濒临红温。

#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;
}

后言

审核大大求过，第一篇捏