AtCoder Beginner Contest 400

C

给出$n$, 求$1 \leq 2^{a} \times b^{2} \leq n$的个数. (a,b 均为正整数)

$1 \leq n \leq 10^{18}$

首先, 确定一下每个数的变化范围:

• $a$: 当$b$最小, $n$最大时, 可以取得最大值$\log_{2}{10^{18}} \approx 59.79471$
• $b$: 同理, $b$的最大值为$\sqrt{10^{18}} = 10^9$

这样的话, 可以把变化范围较小的$a$单独提取出来, 只留下$b$这个变量, 原式变为$0 < b \leq \sqrt{\frac{n}{2^a}}$

得到如下代码

void solve() {
    long long n;
    std::cin >> n;

    long long ans = 0;
    for (long long i = 1; i < 60; i++) {
        long long a = 1LL << i;
        long long b = sqrtl((long double)n / a);
        ans += b;
    }
    std::cout << ans;
}

这样只需要枚举变化范围较小的$a$就可以快速算出符合条件的数了.

但是, 还有一个问题, 会有数被重复计算.

思考, 为什么会造成重复:

当$a$大于$2$时, $2^a \times b^2$可以写成$2^{a-2} \times ({2b})^{2}$

这意味着什么呢, 这意味着后面的数全都可以转化为$2^{a-2k} \times (2^k \times b)^{2}$, 也就是说, 只有$a$为$1$或者是$2$的时候才不会重复.

最终代码:

void solve() {
    long long n;
    std::cin >> n;

    long long ans = 0;
    for (long long i = 1; i <= 2; i++) {
        long long a = 1LL << i;
        long long b = sqrtl((long double)n / a);
        ans += b;
    }
    std::cout << ans;
}

上面的代码可化简为

void solve() {
    long long n;
    std::cin >> n;
    long long ans = 0;
    ans += (long long)sqrtl((long double)n / 2);
    ans += (long long)sqrtl((long double)n / 4);
    std::cout << ans;
}

过几天就要打比赛了, 我现在还在琢磨为什么我的use namespace std;跑不起来.(C++中是using namespace std;)