「Note」杜教筛

大抵算个套路。

$\mathbb{Editorial}$

给一个积性函数 $f$ ， 要求 $f$ 前缀和。
即是求 $\sum_{i = 1}^{n} f(i)$ 。 但是当 $n$ 很大时，直接线筛的时间复杂度会很大。
杜教筛利用了狄利克雷卷积的性质，建立方程，将比较难直接算的函数，转化成一些简单函数的运算求解。

具体地说，首先把要求的结果 $\sum_{i = 1}^n f(i)$ 设为 $S(n)$ 。
然后再找一个积性函数 $g(i)$ ，利用卷积，可以知道
$$ \begin{aligned} &\sum_{i = 1}^{n} (f * g)(i) \\ =&\sum_{i = 1}^{n} \sum_{d \mid i} f(d) g(\frac{i}{d}) \\ =&\sum_{d = 1}^{n} g(d) \sum_{i = 1}^{\lfloor{\frac{n}{d}}\rfloor} f(i) \\ \end{aligned} $$

马上可以发现 $$\sum_{i=1}^{ \lfloor{\frac{n}{d}} \rfloor}f(i)$$ 可以替换成 $$S(\lfloor{\frac{n}{d}}\rfloor)$$ 。
那么原式就是 $$\sum_{d=1}^{n} g(d)S(\lfloor{\frac{n}{d}}\rfloor)$$ 。
我想要的是 $$S(n)$$ 。这个式子里有 $$g(1)S(n)$$ 。
那么找到 $$g(1)S(n)$$ 就找得到 $$S(n)$$ 了。这个可以通过 $$\sum_{d = 1}^{n} g(d) S(\lfloor{\frac{n}{d}}\rfloor) - \sum_{d = 2}^{n} g(d) S(\lfloor{\frac{n}{d}}\rfloor)$$ 得到。

再来一波回代， 得到 $$S(n) = \frac{ \sum_{i = 1}^{n} (f * g)(i) - \sum_{d = 2}^{n} g(d) S(\lfloor{\frac{n}{d}}\rfloor)}{g(1)}$$ 。

你可以选择一个合适的 $g$ 使得卷积可以飞快的算出来，假设算卷积的时间复杂度为 $\mathcal{O}(1)$ 。 那总共的时间复杂度可以达到 $\mathcal{O}(n^{\frac{3}{4}})$ , 比线性快得多。

$\mathcal{Lucas的数论}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

先记一个结论。
$$d(ij) = \sum_{x \mid i} \sum_{y \mid j }[\gcd(x, y)]$$
于是这道题就可做了。