数论分块
数论分块是一个很常用的技巧。我们考虑\(\lfloor n/i\rfloor\)的值，显然只有\(O(2\sqrt n)\)种。因为当\(n\le \sqrt n\)时，值显然有\(\sqrt n\)种。当\(n>\sqrt n\)时，值\(\le \sqrt n\)，最多也只有\(\sqrt n\)种。所以我们可以枚举出每一段\(\lfloor n/i\rfloor\)相同的区间，以解决实际问题。具体方法如下：
\(for\space l=1;l\le n;l=r+1\)
{\(d=n/l;r=n/d;\) \(do\space something...\) }
大概就是枚举左端点\(l\)，求出\(n/l=d\)和右端点\(r=n/d\)，显然是正确的。这个技巧在实际问题中有很大作用。
数论函数
积性函数与加性函数
定义
若函数\(f\)的定义域为\(N^*\)，则称\(f\)为数论函数。
若数论函数\(f\)满足\(f(ab)=f(a)+f(b)(gcd(a,b)=1)\)，则称\(f\)为加性函数。特别的，若\(f\)满足\(f(ab)=f(a)+f(b)\)，则称\(f\)为完全加性函数。
若数论函数\(f\)满足\(f(ab)=f(a)\times f(b)(gcd(a,b)=1)\)，则称\(f\)为积性函数。特别的，若\(f\)满足\(f(ab)=f(a)\times f(b)\)，则称\(f\)为完全积性函数。
一些简单数论函数
\(id_k(n)=n^k\)，叫做幂函数，是完全积性函数。特别的，\(id_1(n)=id(n)=n\)，叫做恒等函数；\(id_0(n)=1(n)=1\)，叫做常数函数。
\(\epsilon(n)=[n=1]\)，叫做单位函数，是完全积性函数。
\(\varphi(n)=\sum_{i=1}^n[gcd(i,n)=1]\)，叫做欧拉函数，是积性函数。若\(n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}\)，则\(\varphi(n)=n\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}...\frac{p_k-1}{p_k}\)。
\(\mu(n)=\begin{cases}(-1)^k & n=p_1p_2...p_k\\0 & n\ne p_1p_2...p_k \end{cases}\)，叫做莫比乌斯函数，是积性函数。
\(\sigma_k(n)=\sum_{d|n}d^k\)，叫做除数函数，是积性函数。特别的，\(\sigma_0(n)=d(n)=\sum_{d|n}1\)，叫做约数函数；\(\sigma_1(n)=\sigma(n)=\sum_{d|n}d\)，叫做约数和函数。显然，若\(n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}\)，则\(d(n)=(e_1+1)(e_2+1)...(e_k+1),\sigma(n)=\frac{p_1^{e_1+1}-1}{p_1-1}\frac{p_2^{e_2+1}-1}{p_2-1}...\frac{p_k^{e_k+1}-1}{p_k-1}\)
\(\omega(n)=k(n=p_1^{e_1}p_2^{e_2}...p_k^{e_k})\)，叫做质因子函数。是加性函数。
求法
每个函数在单点求值时都有自己的专门求法。线性筛是同时求\(1\sim n\)的常用方法。总的来说分三类处理：\(i\)为质数直接求，\(i\space mod\space prime_j=0\)的和\(i\space mod\space prime_j\ne 0\)的仔细求。一类比较难的就是\(\sigma_k(n)\)的线性筛。对于\(d(i)\)，我们记一下\(i\)最小质因子的个数即可；对于\(\sigma_k(i)\)，我们记一下\(i\)最小质因子的若干次幂，用等比数列即可处理。
狄利克雷卷积
定义与性质
定义\(f*g=h\)为数论函数\(f\)和\(g\)的狄利克雷卷积，\(h(n)=\sum_{d|n}f(d)g(n/d)\)。
显然，这个运算满足交换律和结合律。
容易证明，两个积性函数的卷积还是积性函数，所以我们在研究两个积性函数的卷积时，可以只考虑\(n=p^e\)的情况。但是注意，狄利克雷卷积是对任意数论函数都使用的。
有一个小性质是，\(f*\epsilon=f\)，那么，若\(f*g=\epsilon\)，那我们定义\(f,g\)互为狄利克雷卷积逆。所以，如果\(a*f=h\)，那么\(a*(f*g)=a*\epsilon=a=g*h\)。
一些常用结论
\(1\) \(\mu*1=\epsilon\)(莫比乌斯反演常用)
显然，\(\mu(p^e)*1(p^e)=\mu(1)+\mu(p)=0\)。所以\(\mu*1\)只在\(n=1\)时有值\(1\)，即为\(\epsilon\)。
所以，我们推广一下。\(f=g*1\)和\(g=f*\mu\)显然是充要条件。这在后面的莫比乌斯反演中是十分重要的。
\(2\) \(\mu*id=\varphi,id=\varphi*1\)
先感性理解一下，左边的类似于容斥，用\(1-2-3-5+23+25+35...\)。若想求\(1\sim n\)内与\(n\)互质的数个数，就求\(n/1-n/2-n/3-n/5+n/(2*3)+n/(2*5)+n/(3*5)...\)。右边的就按\(gcd(i,n)=d\)来分类，\(gcd(i,n)=d\)的显然有\(\varphi(n/d)\)个，加起来即可。
理性一点就是\(\mu(p^e)*id(p^e)=p^e-p^{e-1}=\varphi(p^e)\)，那么\(\mu*id=\varphi,id=\varphi*1\)。要学会这样的推导方法。
\(3\) \(1*1=d,1*d=\sigma\)
狄利克雷前缀和
真·狄利克雷前缀和
\(P5495\)
考虑每个质因子，则这就是一个类似前缀和的过程。考虑所有质因子，则这就是一个类似高维前缀和的过程。我们枚举每个质数，做一个前缀和即可，复杂度\(O(nloglogn)\)。
狄利克雷前缀和的拓展
\(1\) 求\(b_i=\sum_{i|k,k\le n}a_k\)
简单，做个后缀和即可。
\(2\) 求\(b_i=\sum_{k|i}a_k\mu(i/k)\)
把前缀和改为差分即可。
\(3\) 对于数论函数\(f\)和积性函数\(g\)，求\(f*g\)
把前缀和改成\(01\)背包即可，复杂度还是\(O(nloglogn)\)。
莫比乌斯反演
容斥的"山寨"理解
还是感性地用容斥来理解理解。
\(P2158\)
转化过来就是求\(\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1]\)。这题可以用调和级数求\(gcd=k\)的对数，也可以转变为\(2\sum_{i=1}^n\varphi(i)-1\)，但我们不这么干。
运用容斥，转变为\(\sum_{d=1}^n\mu(d)\lfloor n/d\rfloor^2\)，预处理\(\mu\)，复杂度\(O(n)\)。
像这样运用容斥，我们就可以解决最基本的莫比乌斯反演问题了。
"高级"而广泛的理解
想一想你用上面的方法做不出来的问题，形式无非是求\(\sum_{i_1}\sum_{i_2}...\sum_{i_n}f(gcd(i_1,i_2,...,i_n))h(i_1,i_2,...,i_n)\)。这种问题的解法换汤不换药。
不妨设\(f=g*1\)，则\(g=f*\mu\)，那原式\(=\sum_{i_1}\sum_{i_2}...\sum_{i_n}\sum_{d|i_1,i_2,...,i_n}g(d)h(i_1,i_2,...,i_n)=\sum_{d}g(d)\sum_{d|i_1}\sum_{d|i_2}...\sum_{d|i_n}h(i_1,i_2,...,i_n)\)。这样，预处理好\(g\)，我们就能很方便地解决问题了，这就是所谓的莫比乌斯反演。
例如，\(P2398\)。
这题可以用调和级数求出\(gcd=k\)的对数，也可以转化为\(\sum_{i=1}^ni(2\sum_{j=1}^{n/i}\varphi(j)-1)\)，但我们不这么干。
运用莫反，\(ans=\sum_{d=1}^n\varphi(d)\lfloor n/d\rfloor^2\)，预处理\(\mu\)，复杂度\(O(n)\)。
像这样，一些更高级的数论问题就解决了。
关于\(lcm\)的事情
以\(P1829\)为例。
将\(lcm\)化回\(gcd\)，原式\(=\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}\)。设\(f(n)=\frac{1}{n}\)，则\(g(n)\)可以求出为\((1-p_1)(1-p_2)...(1-p_k)/n(n=p_1^{e_1}p_2^{e_2}...p_k^{e_k})\)，原式等于\(\sum_dg(d)d^2s(n/d)s(m/d)\)，其中\(s(n)\)表示\(1\sim n\)的和。发现\(g(d)d^2\)是整数，于是设\(g(d)d^2=h(d)\)，我们只需预处理\(h(d)\)即可，复杂度\(O(n)\)。