前言：发现最近都没怎么写博客，，，赶紧发篇以前记的笔记凑凑数
卷积
卷积定义：
如果有数论函数(f, g), 那么它们卷积的第(n)项为((f * g) (n)),设这个卷出来的新函数为h，那么有
$$h(n) = sum_{k | n} f(k) g(n / k) = sum_{ij = n}f(i) g(j)$$
一些性质:
1,积性函数的卷积还是积性函数
证明： 现有(f, g)为积性函数，且(gcd(p, q) == 1),求证(h(p) cdot h(q) = h(qp).)
$$h(p) cdot h(q) = sum_{ab = p}f(a) g(b) cdot sum_{cd = q}f(c) g(d)$$
$$= sum_{a} f(a) g(frac{p}{a}) sum_{c} f(c) g(frac{q}{c})$$
$$= sum_{a} sum_{c} f(a) f(c) g(frac{p}{a}) g(frac{q}{c})$$
$$= sum_{a} sum_{c} f(ac) g(frac{pq}{ac})$$
因为(ac cdot frac{pq}{ac} = pq),所以
$$sum_{a} sum_{c} f(ac)g(frac{pq}{ac}) = sum_{ac | pq} f(ac)g(frac{pq}{ac})$$
$$= sum_{x|pq}f(x)g(frac{pq}{x}) = h(pq)$$
常见狄利克雷卷积：
(id = phi * 1)
(d = 1 * 1)
(sigma = id * 1)
(e = 1 * mu)
(phi = id * mu)
有趣的事情：
1，FFT(多项式乘法)就是在求卷积。
可以把(f,g)分别看做两个多项式，(f(i))表示(x^i)的系数，(g(i))同理。
那么卷出来的(h(i))就等于两式相乘后(x^{i})的系数，因为卷积定义里面(h(k))就要加上满足(ij = k)的(f(i) g(j)).
杜教筛
目的：在低于线性的时间内求积性函数前缀和
算法：
设(S(n) = sum_{i = 1}^{n}f_{i}).
设有一个积性函数(g(i)).则：
$$sum_{i = 1}^{n}(g * f)(i) = sum_{i = 1}^{n} sum_{d | i} g(d)f(frac{i}{d})$$
因为当(d | i)时会统计到(g(d)f(frac{i}{d})),因此直接枚举(d)和(i = frac{i}{d}),(i)的最大值为(frac{n}{d}),因为要满足(i cdot d le n).所以：
$$原式= sum_{d = 1}^{n}g(d) sum_{i = 1}^{frac{n}{d}}f(i) = sum_{d = 1}^{n}g(d)S(frac{n}{d})$$
所以：
$$sum_{i = 1}^{n}(g * f)(i) = sum_{d = 1}^{n}g(d)S(frac{n}{d})$$
因为我们有：
$$g(1)S(n) = sum_{i = 1}^{n}g(i)S(frac{n}{i}) - sum_{i = 2}^{n}g(i)S(frac{n}{i})$$
带入上式得：
$$g(1)S(n) = sum_{i = 1}^{n}(g * f)(i) - sum_{i = 2}^{n}g(i)S(frac{n}{i})$$
因此我们只需要找到一个合适的(g)，带入上式，使得(sum_{i = 1}^{n}(g * f)(i))可以快速计算，那么就只需要对(sum_{i = 2}^{n}g(i)S(frac{n}{i}))进行求解就可以得到(S(n)),而这个式子中的(S(frac{n}{i}))是可以整数分块求的。
于是就可以做到(O(n^{frac{3}{4}}))求解了。
同时为了降低复杂度，可以先预处理一部分(S)值。通过证明可得：设我们当前预处理了前(k)个S，那么当(k)取到(n^{frac{2}{3}})时可以使得整体复杂度降为(n^{frac{2}{3}}).(后面部分记忆化求解)
关于记忆化：
1，可以使用map/hash解决。
2,或者观察到对于同一个(S(n)),我们所有要求的(S)值都是形如(S(frac{n}{x}))的，并且我们知道(lfloor{ frac{lfloor{frac{n}{x}}
floor}{y} }
floor = lfloor {frac{n}{xy}}
floor),因此对于同一个(n),我们求的所有(S(x))都可以表示为(S(frac{n}{x})),因此设(now = frac{n}{x})。那么：
1，对于(now <= n^{frac{2}{3}}),我们已经预处理出来了。
2，对于(now > n^{frac{2}{3}})，因为(now > n^{frac{2}{3}}),所以(x = frac{n}{now} <= n ^ {frac{1}{3}}),因此我们可以令(sum[x] = S(frac{n}{x}))。即若我们有(S(now)) 其中$now > n ^ {frac{2}{3}} $，那么我们可以把这个值存入 (sum[frac{n}{now}]).
注意：但这样的话，虽然减少一个log，但若有多个不同n值，则每次处理一个新的n值时就需要清空S数组。
因为虽然对于同一个n值，我们要求的所有S的下标都可以表示为 (frac{n}{x})，但不是任意一个数都可以被表示为 (frac{n}{x}) 的，
如果这个时候的另一个(n)恰好不能被表示，那么答案就会出错