（〇）前置知识
1.数论的基础知识(关于质数，约数)
2.二项式定理
3.数论分块*
4.积性函数*
5.(Dirichlet)卷积*
6.莫比乌斯函数*
注：带"*"号的本文会具体阐述
（一）数论分块
引理1:
这个公式比较容易理解，不详细阐述了。
略证一下:
(dfrac{a}{b}=lfloordfrac{a}{b} floor+r(0leq r<1))
(lfloordfrac{a}{bc} floor=lfloordfrac{a}{b}cdotdfrac{1}{c} floor=lfloordfrac{lfloorfrac{a}{b} floor}{c}+dfrac{r}{c} floor=lfloordfrac{lfloorfrac{a}{b} floor}{c} floor)
引理2：
这个引理描述了(lfloor dfrac{n}{d} floor)的解的集合大小不会超过(2sqrt{n})
容易证明。
由此，我们可以得到一个算法：数论分块。
先来看这样的一个问题：求(sumlimits_{i=1}^{n} lfloordfrac{n}{i} floor)
如果我们枚举每个(i)，那么显然时间复杂度是(Theta(n))，有没有更快的算法？
根据引理2我们可以知道，对于所有(lfloordfrac{n}{i} floor)，至多只有(2sqrt{n})个不同的解。
直观感受一下:
不难发现，(lfloordfrac{n}{i} floor)的值是一段一段的(在一个连续的区间内)，而这个区间的右端点恰好是(lfloordfrac{n}{lfloorfrac{n}{i} floor} floor)的值。
证明略。代码如下:
for(int l = 1, r; l <= n; l = r+1){
r = n/(n/l);
f(l, r);
}
[拓展]二维数论分块
什么是二维数论分块？
举个例子，如果我们要在求(lfloordfrac{n}{i} floor)的同时求出(lfloordfrac{m}{i} floor)，这时就需要用到二维数论分块。
代码实现很简单只需要加上一行:
for(int l=1, r; l <= min(n, m); l = r+1){
r = min(n/(n/l), m/(m/l));
f(l, r);
}
（二）积性函数
定义
若函数(f(n))满足(f(1)=1)且(forall x,yin mathbb{N_+},gcd(x,y)=1)都有(f(xy)=f(x)f(y))，则(f(n))为积性函数。
若函数(f(n))满足(f(1)=1)且(forall x,yinmathbb{N_+})都有(f(xy)=f(x)f(y))，则(f(x))为完全积性函数。
性质
若(f(x))和(g(x))均为积性函数，则以下函数也为积性函数。
设(x= prod p_{i}^{k_i})其中(p_i)是质数
若(F(x))为积性函数，则有(F(x)=prod F(p_i^{k_i}))。
若(F(x))为完全积性函数，则有(F(x)=prod F(p_i)^{k_i})
举例
单位函数：(varepsilon=[n=1])(完全积性函数)
恒等函数：(operatorname{id}_k(n)=n^k)其中(operatorname{id}_1(n))简记作(operatorname{id}(n))(完全积性函数)
常数函数：(operatorname{1}(n)=1)(完全积性函数)
除数函数：(sigma_k(n)=sumlimits_{d|n}d^k)(积性函数)
欧拉函数：(varphi(n)=sumlimits_{i=1}^{n}[gcd(i,n)=1])(积性函数)
（三）(Dirichlet)卷积
又称“狄利克雷卷积”。
定义
定义两个数论函数(f,g)的(Dirichlet)卷积为:
性质
(Dirichlet)卷积满足一下运算规律:
1.交换律：(f*g=g*f)
2.结合律：((f*g)*h=f*(g*h))
3.分配律：(f*(g+h)=f*g+f*h)
4.(f*varepsilon=f)其中(varepsilon)是(Dirichlet)卷积的单位元
例子(公式)
（四）莫比乌斯函数
定义
(mu)为莫比乌斯函数，定义为
其中(omega(n))表示(n)的本质不同质因子个数，它也是一个积性函数。
性质(敲黑板)
除了积性函数的性质以外，莫比乌斯函数还有如下性质
即
证明:
设(n=prodlimits_{i=1}^{k}p_i^{c_i},n'=prodlimits_{i=1}^kp_i)
那么(sumlimits_{d|n}^kmu(d)=sumlimits_{d|n'}^kmu(d))
(解释：因为由莫比乌斯函数的定义可知，当(c_i>1)时，(mu(p^{c_i})=0))
(sumlimits_{d|n'}=mu(d)=sumlimits_{i=0}^kC_k^icdot(-1)^i)
（解释：因为(n')的因子全是由质数(p_i)组成的，所以在(n')的(k)个质因子中选出(i)个可以组合成(n')的所有因子，然后根据选出的质因子个数判断符号是正是负）
((ps):到了这一步有没有发现很像某个定理)
根据二项式定理:
得:
(sumlimits_{i=0}^{k}C^i_kcdot(-1)^i=sumlimits_{i=0}^{k}dbinom{k}{i} imes1^{n-i} imes(-1)^i=(1-1)^k=0^k)
该式子的值在(k=0)时即(n=1)时值为(1)，否则为(0)。所以，
(sumlimits_{d|1}^nmu(d)=[n=1]=varepsilon(n),mu*1=varepsilon)
线性筛
问题来了，知道了性质，如何求莫比乌斯函数？
使用线性筛。线性筛基本可以求所有的积性函数，莫比乌斯函数也在其中。
代码：
mu[1] = 1;
for(int i=2; i<=N; i++){
if(!vis[i]) prime[++cnt] = i, mu[i] = -1;//找出素数，素数的莫比乌斯函数值为-1
for(int j=1; j<=cnt and i*prime[j] <= N; j++){
vis[i*prime[j]] = true;//标记以当前素数为最小质因子的合数
if(i%prime[j] == 0){
mu[i*prime[j]] = 0;//如果该合数由两个相同的质因子，莫比乌斯函数值为0
break;
}
mu[i*prime[j]] = -mu[i];
}
}
（五）莫比乌斯反演
设(f(n),g(n))为两个数论函数，
如果有(f(n)=sumlimits_{d|n}g(d))，那么有(g(n)=sumlimits_{d|n}mu(d)cdot f(dfrac{n}{d}))
如果有(f(n)=sumlimits_{n|d}g(d))，那么有(g(n) = sumlimits_{d|n}mu(dfrac{d}{n})cdot f(d))
换一种更加简洁的写法，狄利克雷卷积:
(f=g*1iff f*mu=g)
另外几个常用公式
(varepsilon=mu*1iff [x=1]=sumlimits_{d|n}mu(d))
(varphi*1=operatorname{id}iff varphi=operatorname{id}*mu)
好了，公式看了这么多，来做几组练习。
练习(练习中设(Nleq M))
1.求(sumlimits_{i=1}^Nsumlimits_{j=1}^{M}[gcd(i,j)=1])
解：原式(=sumlimits_{i=1}^{N}sumlimits_{j=1}^{M}varepsilon(gcd(i,j))\=sumlimits_{i=1}^{N}sumlimits_{j=1}^{M}sumlimits_{d|(i,j)}mu(d)\=sumlimits_{d=1}^{N}mu(d)cdotsumlimits_{i=1}^{lfloorfrac{N}{d} floor}sumlimits_{j=1}^{lfloorfrac{M}{d} floor}1\=sumlimits_{d=1}^{N}mu(d)lfloordfrac{N}{d} floorlfloordfrac{M}{d} floor)
2.求(sumlimits_{i=1}^{N}sumlimits_{j=1}^{M}[gcd(i,j)=k])
解：原式(=sumlimits_{i=1}^{lfloorfrac{N}{k} floor}sumlimits_{j=1}^{lfloorfrac{M}{k} floor}[gcd(i,j)=1])
然后用与练习1一样的方式求解即可。
3.求(sumlimits_{i=1}^{N}sumlimits_{j=1}^{M}operatorname{lcm}(i,j))
解：原式(=sumlimits_{i=1}^{N}sumlimits_{j=1}^{M}dfrac{ij}{gcd(i,j)}\=sumlimits_{d=1}^{N}sumlimits_{i=1}^{N}sumlimits_{j=1}^{M}[gcd(i,j)=d]dfrac{ij}{d}\=sumlimits_{d=1}^{N}dsumlimits_{i=1}^{lfloorfrac{N}{d} floor}sumlimits_{j=1}^{lfloorfrac{M}{d} floor}ij[gcd(i,j)=1]\=sumlimits_{d=1}^{N}dsumlimits_{i=1}^{lfloorfrac{N}{d} floor}sumlimits_{j=1}^{lfloorfrac{M}{d} floor}ijsumlimits_{x|(i,j)}mu(x)\=sumlimits_{d=1}^{N}dsumlimits_{x=1}^{lfloorfrac{N}{d} floor}mu(x)x^2sumlimits_{i=1}^{lfloorfrac{N}{dx} floor}sumlimits_{j=1}^{lfloorfrac{M}{dx} floor}ij\=sumlimits_{d=1}^{N}dsumlimits_{x=1}^{lfloorfrac{N}{d} floor}mu(x)x^2dfrac{lfloorfrac{N}{dx} floor(lfloorfrac{N}{dx} floor+1)lfloorfrac{M}{dx} floor(lfloorfrac{M}{dx} floor+1)}{4})
真不容易~
留坑待补。