没有写一些概念（？（（（
我是梅比乌斯厨=莫比乌斯厨=牲畜（暴论。
前置芝士
积性分解
对于积性函数 \(f\)，给出 \(n=\prod_{i=1}^m p_i^{c_i}\)。有 \(f(n)=\prod_{i=1}^m f(p_i^{c_i})\)。意思是跟 质因子 & 幂次 相关度较高 。
狄利克雷卷积
两个数论函数（这里理解成值域为正整数）卷乘一个新的数论函数，记作 \(f*g\)。满足
-
这玩意满足 交换 & 结合律。数论函数 \(\epsilon(n)=[n=1]\)。任意数论函数 \(f*\epsilon=f\)。
-
计算上面除了按照定义也可以枚举因数的倍数。
-
两个积性函数的卷积仍是积性函数。
卷积逆元
给出 \(f\) 满足 \(f(1)=1\)，\(f\) 的逆元 \(g=f^{-1}\) 满足 \(f*g=\epsilon\)。
首先 \(g(1)=1\)，对于 \(n>1\) 求 \(g(n)\)
- 积性函数的逆仍是积性函数。
莫比乌斯反演
莫比乌斯函数
有函数 \(I(n)=1\)，莫比乌斯函数 \(\mu=\epsilon^{-1}\)。
写出在幂处的取值，是研究积性函数的通用方法。
-
\(\mu(1)=1\)
-
\(\mu(p)I(1)+\mu(1)I(p)=0\) 意思是 \(\mu(p)=-1\)
-
\(k>1,\sum_{i=0}^k\mu(p^i)=0\)，归纳就是 \(\mu(p^k)=0\)
当 \(n\) 没有平方因子时， \(\mu(n)=-1^{x}\)，其中 \(x\) 是 \(n\) 的素因子数目。otherwise, \(\mu(n)=0\)。
\(\mu\) 这个跟 *** 一样可爱的东西用卷积逆就可以 \(O(n\log n)\) 卷出来了。也可以线性筛递推捏。具体的递推 \(\mu(n)\)，\(p|(n/p)\) 的话 \(\mu(n)=0\) 否则就是 \(\mu(n)=-\mu(n/p)\)。
int p[M], top, mu[M], vis[M];
vis[1]=1, mu[1]=1;
for(int i=2; i<=N; ++i) {
if(!vis[i]) p[++top]=i, mu[i]=-1;
for(int j=1; j<=top&&i*p[j]<=N; ++j) {
int x=i*p[j]; vis[x]=1;
if(i%p[j]!=0) mu[x]=-mu[i];
}
}
约数求和 & 倍数求和
有一定的值域 qwq bwb pwp dwd
对 \(f\) 弄一个可爱的 \(Lsum(f)\) & 一个丑陋的 \(Rsum(f)\)。
按照幂次把数看为高维点这个分别是 前缀|后缀和 >w<
我们再给祂们弄逆操作\(Ldif(Lsum(f))=f,Rdif(Rsum(f))=f\)
差分的计算
给出 \(g=Lsum(f)\)，求 \(f\)。条件等价于 \(g=f*l\)，则 \(f=g*\mu\)。
给出 \(g=Rsum(f)\)，求 \(f\)。
或者容斥也可以捏 >_<
求得 \(\mu\) 的话，计算都是 \(O(n\log n)\) 捏。
gcd 卷积
给出函数 \(f,g\)，记两者的 gcd卷卷卷函数为 \(h\)。满足 \(h(n)=\sum_{\gcd(x,y)=n}f(x)g(y)\)。
求出 \(Rsum(h)\) 然后倍数差分捏。
可以联想 and 卷积，有类似的结论 qwq
如果有些 \(f\) 很厉害的话，可以顺便记录一下最小质因子的次数来递推。
诶 \(n\) 里面质数的幂有多少个呢（？（（（
然后如果求单个 \(f(p^k)\) 的复杂度不超过 \(O(\log n)\) 的话，总复杂度线性。
说句闲话这解决了 lsy 一个珂爱的没有深究的历史遗留的不知道为什么能过问题（？