LOWBIT001 - 杜教筛·lowbit求和

解题思路

这道题是个诱饵题 😏

虽然标题写杜教筛，提示说lowbit是积性函数，但实际上直接枚举lowbit即可秒杀！

核心观察

对于任意正整数 n，lowbit(i) = 2^k 表示 i 的二进制最低非零位。

规律：

• lowbit = 1 的数：1,3,5,7... 共 ⌊n/2⌋ 个
• lowbit = 2 的数：2,6,10,14... 共 ⌊n/4⌋ 个
• lowbit = 4 的数：4,12,20,28... 共 ⌊n/8⌋ 个
• 以此类推

算法

枚举 k 从 0 到 floor(log₂n)：

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

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

参考实现（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 cnt = (n >> k) - (n >> (k + 1));
        ans += cnt * (1LL << k);
    }
    cout << ans << "\\n";
    return 0;
}

样例验证

n	计算过程	结果
1	lowbit(1)=1	1 ✅
7	1×4 + 2×2 + 4×1	12 ✅
10	1×5 + 2×3 + 4×1 + 8×1	23 ✅
100	1×50 + 2×25 + 4×13 + 8×6 + 16×3 + 32×2 + 64×1	376 ✅