杜教筛·lowbit求和

背景

杜教筛是一种高效求数论函数前缀和的算法，其核心思想是利用狄利克雷卷积将复杂求和转化为简单形式。

杜教筛基本公式

对于数论函数 $f(n)$，设其前缀和为 $S(n) = \sum_{i=1}^{n} f(i)$。

若存在函数 $g(n)$ 使得 $f * g = h$（狄利克雷卷积），且 $h(n)$ 的前缀和易求，则：

$$S(n) = \frac{\sum_{i=1}^{n} h(i) - \sum_{i=2}^{n} g(i) \cdot S(\lfloor n/i \rfloor)}{g(1)}$$

经典应用：莫比乌斯函数前缀和

取 $f = \mu$，$g = 1$，则 $f * g = \epsilon$（单位元），有：

$$S(n) = 1 - \sum_{i=2}^{n} S(\lfloor n/i \rfloor)$$

算法实现

// 莫比乌斯函数前缀和的杜教筛实现
unordered_map<long long, long long> mp;
long long S(long long n) {
    if (n < MAXN) return preMu[n];
    if (mp.count(n)) return mp[n];
    long long ans = 1;
    for (long long i = 2, j; i <= n; i = j + 1) {
        j = n / (n / i);
        ans -= (j - i + 1) * S(n / i);
    }
    return mp[n] = ans;
}

---

注意到，lowbit 函数也具有类似的性质。

lowbit(x) = x & (-x) 表示 x 的二进制表示中最低非零位对应的值。

有趣的结论：lowbit 也是一个积性函数！

即对于任意互质的正整数 a, b，有：

$$\text{lowbit}(a \cdot b) = \text{lowbit}(a) \cdot \text{lowbit}(b)$$

---

题目描述

给定正整数 $n$，计算：

$$S(n) = \sum_{i=1}^{n} \text{lowbit}(i)$$

输入格式

一个整数 $n$。

输出格式

一个整数，表示 $S(n)$。

样例

输入

7

输出

12

说明

• lowbit(1) = 1
• lowbit(2) = 2
• lowbit(3) = 1
• lowbit(4) = 4
• lowbit(5) = 1
• lowbit(6) = 2
• lowbit(7) = 1

所以 S(7) = 1+2+1+4+1+2+1 = 12。

提示

利用 lowbit 是积性函数的性质，构造合适的数论变换来求解。

限制

• 时间限制：1 秒
• 内存限制：256 MB