一直不太喜欢数论呢
预警：这篇文章公式里面的1请看做为\mathbf 1，是常数函数
一些定义：（不严谨的话以后有时间再改吧）
- 数论函数：定义域为整数的函数；（理论上数论函数好像是要粗体或者拉丁字母来着？比如\mathbf f。但是百科也没管就不管了）
- 积性函数：如果任意x,y，对于数论函数f均有\gcd(x, y)=1\Rightarrow f(xy) = f(x)f(y)，那么称f为积性函数
- 完全积性函数：如果任意x,y，对于数论函数f均有f(xy) = f(x)f(y)，那么称f为完全积性函数
一些记号：
- d|n：n=kd\quad k\in\mathbb{Z}
- [x] =
(bool)x
然后有一些函数：
- \varepsilon(n) = [n = 1]完全积性函数
- 1(n)=1完全积性函数
- \operatorname{ID}^k(n) = n^k完全积性函数（一般记\operatorname{ID}^1为\operatorname{ID}）
- \sigma_k(n)=\sum\limits_{d|n}d^k积性函数（常用的\sigma_0为除数个数，可记作\operatorname d或\tau）（一般记\sigma_1为\sigma）
- \varphi(n)=\sum\limits_{i=1}^{n}[\gcd(i, n) = 1]积性函数（大名鼎鼎的欧拉函数，表示不超过n与n互质的数个个数）
- \mu(n)积性函数，没写表达式是准备在下面写。
接下来是狄里克雷卷积：
对于数论函数f, g，定义狄里克雷卷积h为h(n)=\sum\limits_{d|n}f(d)g(\dfrac n d)，记为f\times g
我们设个奇怪的东西：\varepsilon = \mu\times 1，这个东西挺有用的，马上就用到。
经过一些奇奇怪怪的过程，我们得到：
\mu(n)=\begin{cases}1&n=1\\ 0&n含有平方因子\\ (-1)^k&n=p_1p_2p_3\dots p_k,p_i为质数且互不相同 \end{cases}
至于这个定义能不能推\varepsilon = \mu\times 1呢，试试：
当n=1显然
当n>1，设n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}
那么\sum\limits_{d|n}\mu(d)1(n) = \mu(1) + \mu(p_1^{a_1})+\cdots+\mu(p_k^{a_k})+\mu(p_1^{a_1}p_2^{a_2})+\cdots+\mu(p_1^{a_1}\cdots p_k^{a_k})
当a_i>1，\mu(p_i^{a_i}\times k) = 0，因此包含a_i>1的项不再计算。
那么\sum\limits_{d|n}\mu(d)1(n) = \mu(1) + \mu(p_1)+\cdots+\mu(p_k)+\mu(p_1p_2)+\cdots+\mu(p_1\cdots p_k)
那么\sum\limits_{d|n}\mu(d)1(n) = 1+\mathbf C_k^1\times(-1)^1+\mathbf C_k^2\times(-1)^2+\cdots+\mathbf C_k^k\times(-1)^k = 0
\square
当然这个没啥大用然而我推了半天，下面的才重要（我想）：
对于给定的数论函数f, g，
f(n) = \sum\limits_{d|n}g(d)\Longleftrightarrow g(n) = \sum\limits_{d|n}\mu(d)f(\dfrac n d)
稍微提醒一下\sum\limits_{d|n}f(d)g(\dfrac n d) = \sum\limits_{d|n}f(\dfrac n d)g(d)
要知道在我的博客里面居中的公式是真心不多的。
不看证明背着就好了
证明看这里吧，不想打公式
接下来是线筛mu：
inline void calc_mu(void)
{
not_prime[1] = true;
mu[1] = 1;//mu(1) = 1
for (int i = 2; i != N; ++i)
{
if (!not_prime[i])
{
mu[i] = -1;//mu(p) = (-1)^1 = -1
primes[++primes[0]] = i;
}
for (int j = 1; j <= primes[0] && primes[j] * i < N; ++j)
{
not_prime[i * primes[j]] = true;
if (i % primes[j] == 0)
{
mu[i * primes[j]] = 0;//contains primes[j]^2
break;
}
mu[i * primes[j]] = -mu[i];//single primes[j]
}
}
}
对了你可能会用到整除分块，我觉得没必要专门拿一篇文章讲了。
我们会经常算f(x) = \sum\lfloor\dfrac n x\rfloor，O(n)的很好想，但是你造吗这个可以用O\sqrt n的时间算出来：
我们想有好多的\lfloor\dfrac n i\rfloor=\lfloor\dfrac n j\rfloor，而且她们是连续的，这时如果我们可以算得她们有多少个，再乘上一个...
一般我们取j=\Big\lfloor\dfrac n {\lfloor\frac n i\rfloor}\Big\rfloor，我们先证明正确性：
\dfrac n i \ge \lfloor\dfrac n i\rfloor\\ \Big\lfloor\dfrac n {\frac n i}\Big\rfloor \le \Big\lfloor\dfrac n {\lfloor\frac n i\rfloor}\Big\rfloor\\ \lfloor i\rfloor = i\le\Big\lfloor\dfrac n {\lfloor\frac n i\rfloor}\Big\rfloor
然后看复杂度：
- x\le\sqrt n,|\lfloor\dfrac n x\rfloor|\le \sqrt n
- x\ge\sqrt n,\lfloor\dfrac n x\rfloor\le\sqrt n\Rightarrow|\lfloor\dfrac n x\rfloor|\le \sqrt n
还有一些好玩的东西：
- \mu\times 1 = \varepsilon说过了
- \varphi\times1 = \operatorname{ID}记住欧拉函数是积性函数，基本定理来一波
- \operatorname{ID}\times\mu = \varphi
- 1\times1=\sigma_0
- 1\times\operatorname{ID}=\sigma
然后是题
因为做题都是靠trick，所以推荐按顺序做：