# 原理

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

\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}

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

# 复杂度

\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}

# 例题

Sum BZOJ – 3944

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

• 尽量 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;
}


#### Remmina

No puzzle that couldn't be solved.