定义域为正整数、陪域为复数的函数
(phi(x))，欧拉函数
也写作：(varphi(x))
含义：小于等于自己的，与自己互质的数的个数
通式：(phi(x)=xprodlimits_{p_i}(1-dfrac{1}{p_i}))，其中(p_i)为(x)的质因数
特殊性质：
举个栗子证明理解一下：
(12)个分数
约分一下
按分母分个类
(mu(x))，莫比乌斯函数
特殊性质：
(epsilon(x))，元函数
(id(x))，单位函数
(I(x))，恒等函数
也记作(1(x)=1)
积性函数
积性函数：对于任意互质的整数(a)和(b)，都有(f(ab)=f(a)cdot f(b))的函数(f)，(f(1)=1)
完全积性函数：对于任意整数(a)和(b) ，都有(f(ab)=f(a)cdot f(b))的函数(f)
以上提到的所有函数均为积性函数，其中(phi,mu)为积性函数，(epsilon,id,I)为完全积性函数
利用积性函数的性质，我们可以进行线性筛
狄利克雷卷积定义两个数论函数的狄利克雷卷积(otimes(ast))
若$h=fast g $
一定要记住这个式子
以下性质（看看就好）：
- 交换律：(fast g=gast f)
- 结合律：(fast (gast h)=(fast g)ast h)
- 分配律：((f+g)ast h=f ast h+gast h)
- ((xf)ast g=x(fast g))
- (epsilonast f=f)
将上述(phi)和(mu)的性质用卷积形式表示，就是
两边同时卷一个(mu)
（这步转化注意使用狄利克雷卷积的性质）
用式子表示，就是
这个式子就是莫比乌斯反演
应用
（以下式子可以用莫比乌斯反演推，但是我懒）
求
先枚举(d)，即(gcd)的因数
注意到(leftlfloordfrac{n}{d} ight floor)只有(sqrt n)种取值，整除分块((O(sqrt n)))加上预处理(mu(O(n)))，可以处理多组询问
整除分块
在(i)到(leftlfloordfrac{n}{leftlfloordfrac{n}{i} ight floor} ight floor)这个范围内，(leftlfloordfrac{n}{i} ight floor)的值是一样的，(i)取到(leftlfloordfrac{n}{leftlfloordfrac{n}{i} ight floor} ight floor+1)时，(leftlfloordfrac{n}{i} ight floor)的值会变小
(leftlfloordfrac{n}{d} ight floor)只有(sqrt n)种取值
利用这个就可以做整除分块了
对于这个式子(sumlimits_{d=1}^{min(n,m)}mu(d)leftlfloorfrac{n}{d} ight floorleftlfloorfrac{m}{d} ight floor)
在(i-min(leftlfloordfrac{n}{leftlfloorfrac{n}{i} ight floor} ight floor,leftlfloordfrac{m}{leftlfloorfrac{m}{i} ight floor} ight floor))的范围内，(leftlfloordfrac{n}{d} ight floorleftlfloordfrac{m}{d} ight floor)的值不变
设 (r=min(leftlfloordfrac{n}{leftlfloorfrac{n}{i} ight floor} ight floor,leftlfloordfrac{m}{leftlfloorfrac{m}{i} ight floor} ight floor))
那么这一段内的和就是(leftlfloordfrac{n}{d} ight floorleftlfloordfrac{m}{d} ight floorcdot sumlimits_{j=i}^{r}mu(j))
对(mu)求一下前缀和，即可(O(1))算出(i-r)的和
inline long long solve(int n,int m){
long long ans=0;
for(int i=1,r;i<=min(n,m);i=r+1){
r=min(n/(n/i),m/(m/i));
ans+=1ll*(n/i)*(m/i)*(musum[r]-musum[i-1]);
}
return ans;
}