用途

用于在 $O(n ^ \frac 2 3)$的时间复杂度内求出 $\sum _ {i = 1} ^ n f(i)$，其中 $f$为积性函数

原理

设 $s(i) = \sum _ {i = 1} ^ n f(i)$

构造积性函数 $g(i)$，设 $f$与 $g$的狄利克雷卷积为 $f * g$

即：

$$(f * g)(i) = \sum _ {d | i} g(d)f(\frac i d)$$

对卷积得到的函数求前缀和：

$$
\begin{equation}
\begin{aligned}
\sum _ {i = 1} ^ n (f * g)(i) &= \sum _ {i = 1} ^ n \sum _ {d | i} g(d) f(\frac i d)\\
&= \sum _ {d = 1} ^ n g(d) \sum _ {d | i} f(\frac i d)\\
&= \sum _ {d = 1} ^ n g(d) \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} f(i)\\
&= \sum _ {d = 1} ^ n g(d) s(\lfloor \frac n d \rfloor)
\end{aligned}
\end{equation}
$$

移一下项就有：

$$g(1) s(n) = \sum _ {i = 1} ^ n (f * g)(i) – \sum _ {d = 2} ^ n g(d) s(\lfloor \frac n d \rfloor)$$

很明显这个东西就能用记忆化搜索去求 $s(n)$了，后面那个 $\sum _ {d = 2} ^ n g(d) s(\lfloor \frac n d \rfloor)$用数论分块就行了

这个构造的 $g$要求比较高，你需要让 $\sum _ {d = 2} ^ n g(d)$很好求，同时需要让 $\sum _ {i = 1} ^ n (f * g)(i)$很好求这是个令人头疼的事情

复杂度

然而我不会算，所以千万别问我怎么算的

根据主定理：

$$
\begin{equation}
\begin{aligned}
T(n) &= O(\sqrt n) + \sum _ {i = 1} ^ \sqrt n T(i) + T(\frac n i)\\
&= \sum _ {i = 1} ^ \sqrt n O(\sqrt i) + O(\sqrt \frac n i)\\
&= O(n ^ \frac 3 4)
\end{aligned}
\end{equation}
$$

如果我们先用线性筛来预处理出 $i \in [1, k]$内的 $s(i)$，那么记忆化搜索的复杂度为 $O(\frac n {\sqrt k})$，预处理复杂度为 $O(k)$，因此 $k = n ^ \frac 2 3$时取到最优复杂度，为 $O(n ^ \frac 2 3)$

实现

一般实现的时候用 map 来进行记忆化就行了，因为需要记忆化的元素个数为 $n ^ \frac 1 3$，一般不会超过 $10 ^ 4$（否则 $n ^ \frac 2 3$就已经超过 $10 ^ 8$的级别了），带个小 $\log$问题不大

如果用哈希表应该会更快，但是没试过

当然也有更好的记忆化方法，就是对于 $i$记忆化 $s(\frac n i)$的值，$i$的取值范围为 $[1, n ^ \frac 1 3]$

这是因为你每次都会去搜当前的数字除以一个数向下取整

且 $\lfloor \frac {\lfloor \frac n a \rfloor} b \rfloor = \lfloor \frac n {ab} \rfloor$

还有当 $i \leq \sqrt n$时有 $\lfloor \frac n {\lfloor \frac n i \rfloor} \rfloor = i$

所以这样表示状态是不会出错的

例题

Sum BZOJ – 3944

求欧拉函数 $\varphi$和莫比乌斯函数 $\mu$的前缀和，$n \leq 2 ^ {31} – 1$

经典的杜教筛模板题

对于两者，都构造 $g(i) = 1$

因为：

$$(\varphi * g)(i) = i$$
$$(\mu * g)(i) = [i = 1]$$

非常愉快

但这题似乎有点卡常（BZOJ 算的是总时限另当别论），有这么几个优化技巧：

• 尽量 unsigned int 存，避免 long long
• $\mu$的前缀和用 int 存
• 不需要进行两次记忆化搜索，因为两棵 dfs 树是一模一样的，在同一个 dfs 里同时计算两个函数值就行了
• 由于有多组询问，可以适当地增大预处理的数据量

代码：

#include <bits/stdc++.h>

#define PS (2000000)
#define SS (1075)

using namespace std;

typedef long long LL;
typedef unsigned int UI;

template<typename _Tp> inline void IN(_Tp &dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int testcase, p[PS / 10], mp[PS], ms[SS];

UI n;

LL pp[PS], ps[SS];

bool book[PS], vis[SS];

void preWork()
{
    pp[1] = mp[1] = 1;
    for (int i = 2; i < PS; i += 1)
    {
        if (!book[i]) p[++p[0]] = i, pp[i] = i - 1, mp[i] = -1;
        for (int j = 1, k; j <= p[0]; j += 1)
        {
            k = i * p[j];
            if (k >= PS) break;
            book[k] = 1;
            if (i % p[j]) pp[k] = pp[i] * pp[p[j]], mp[k] = mp[i] * mp[p[j]];
            else { pp[k] = pp[i] * p[j], mp[k] = 0; break; }
        }
    }
    for (int i = 2; i < PS; i += 1) pp[i] += pp[i - 1], mp[i] += mp[i - 1];
}

LL phi;

int mu;

void dfs(UI x)
{
    if (x < PS) { phi = pp[x], mu = mp[x]; return; }
    LL &pf = ps[n / x]; int &mf = ms[n / x];
    if (vis[n / x]) { phi = ps[n / x]; mu = ms[n / x]; return; }
    vis[n / x] = 1, pf = (1ll * x * (1 + x)) >> 1, mf = 1;
    for (UI i = 2, j; i <= x; i = j + 1)
    {
        j = x / (x / i), dfs(x / i);
        pf -= (j - i + 1) * phi, mf -= (j - i + 1) * mu;
    }
    phi = pf, mu = mf;
}

int main(int argc, char const* argv[])
{
    IN(testcase), preWork();
    while (testcase--)
    {
        IN(n), memset(vis, 0, sizeof(vis)), dfs(n);
        printf("%lld %d\n", phi, mu);
    }
    return 0;
}