算法分析

这是一道诱饵题。

题目描述中提到杜教筛、积性函数，似乎暗示需要使用高级数论算法。但实际上，本题有非常简单的 $O(\log n)$ 解法。

核心观察

对于任意正整数 $x$，有 $\text{lowbit}(x) = 2^k$，其中 $k$ 为 $x$ 二进制表示中末尾连续 $0$ 的个数。

所以：

$$\sum_{i=1}^{n} \text{lowbit}(i) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k \times \left\lfloor \frac{n}{2^k} \right\rfloor - \left\lfloor \frac{n}{2^{k+1}} \right\rfloor$$

参考实现（C++）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long n;
    if (!(cin >> n)) return 0;
    
    long long ans = 0;
    for (long long k = 0; (1LL << k) <= n; k++) {
        long long pow2 = 1LL << k;
        long long cnt = (n >> k) - (n >> (k + 1));
        ans += cnt * pow2;
    }
    
    cout << ans << '\\\n'\;
    return 0;
}

复杂度分析

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(1)$