前言
积性函数是OI中的数论题的重要组成部分 （一般都是涉及到各种因数啊，倍数啊，gcd啊
前置知识
整除分块（引理）
有下面这样一个式子：
求这样一个东西需要多久？(O(n))？
仔细观察，我们会发现 (left lfloor {n over i} ight floor) 会有相同的取值。
比如：({18over 7}={18over 8}={18over 9}=2)
有这样一个结论 (left lfloor {n over i} ight floor) 最多有 (2sqrt n) 种取值
所以可以 (O(sqrt n)) 算出答案。
莫比乌斯函数
定义
莫比乌斯函数，像这样 (mu(n))
例如
一个性质
也就是当n=1是它的值才为1，其他情况都为0 （根据定义应该不难推出吧（逃
欧拉函数
定义
欧拉函数，就像是这样 (varphi(n))
意思是说在 1 到 n，与 n 互质的数有多少个。
比如 (varphi(1)=1)，(varphi(7)=6)，(varphi(12)=4)
表达式
(p_i)为(p)的第(i)个质因数，k为质因数个数
其实很简单，就是个容斥
n个数，减去p1的倍数，p2的倍数……再加回p1p2的倍数，减回p1p2p3的倍数……
一个性质
记着就好，就懒得贴证明了 （其实也不难（逃
回归正题——积性函数
什么是积性函数
一个函数(f(n))，如果 (f(nm)=f(n)f(m)) （n与m互质），那么它就是一个积性函数
另外，如果n、m不互质，上式依然满足，那么它是一个完全积性函数
很显然，上面的莫比乌斯函数和欧拉函数都属于积性函数
其他常见的积性函数
(e(n)=[n=1]) （元函数）
(1(n)=1)
(id(n)=n)
(d(n)=sum_{d|n}1)（因数个数）
(sigma(n)=sum_{d|n}d) （因数和）
狄利克雷卷积
在这类OI题里，总是会出现 (sum_{d|n}f(d)) 这样的式子，这下，就该狄利克雷卷积出场了
两个积性函数 (f(n)) ，(g(n))，它们的狄利克雷卷积记为 (f*g(n)) 是
或者
运算法则
交换律
把 n/d 换成 d 很容易解决
结合律
常见卷积
仔细观察 (sum_{d|n}f(d)=sum_{d|n}f(d) imes1=sum_{d|n}f(d)1(frac{n}{d})=f*1(n))
再回到开始的两个性质
所以可得 (mu*1(n)=e(n))，(varphi*1(n)=id(n))
多试几次还可以得出（省略括号）
同时有
可以看出，在狄利克雷卷积中(mu)相当于加法中的-1，e相当于0，1相当于1
解题
PS：推式子的技巧
枚举因数变为枚举倍数
莫比乌斯反演
就是
(几乎是废话)
当然，重点不是这个，主要是要在式子中构造一个狄利克雷卷积
莫比乌斯反演常用的就是 (e(n)=mu*1(n))
也就是那个重要性质 (sumlimits _{d|n}mu(d)=[n=1])
多说无用，来例题
还记得开始讲的整除分块吗？
(lfloorfrac{n}{d}
floor) 只有 (2sqrt{n}) 种取值，通过对每种取值分块，预处理出 (mu) 的前缀和，就能 (O(sqrt{n})) 求出答案
代码实现
\ n/(n/i)可以算出 n/i 这个值最后出现的位置 （很简单自己想
for(int i=1,pos;i<=min(n,m);i=pos+1){
pos=min(n/(n/i),m/(m/i));
ans+=(mu[pos]-mu[i-1])*(n/i)*(m/i);
}
其他类似的题都基本这样想