感谢lsy学长来101给我们上课~
Day 1
逆元
对于一个 \(a\)，当 \(ab\equiv1\pmod{m}\) 时我们把 \(b\) 的最小整数解称作 \(a\) 模 \(m\) 的逆元，记作 \(a^{-1}\) 或 \(\frac{1}{a}\)。
接下来我们来看看逆元的求法。
费尔马小定理
如果 \(a\) 是一个整数，\(p\) 是一个质数，则有
\[a^p\equiv a\pmod{p} \]所以对于我们上面要求的形式的话，那么有
\[a^{p-2}\cdot a\equiv 1\pmod{p} \]所以在模数是质数的情况下，我们可以通过 \(O(\log{n})\) 的时间来快速幂求出一个数的逆元。优点是很好写，但是限制会有点大。
扩展欧几里得（exgcd）
扩欧是在基于裴蜀定理之后得到的结论，这里先说一下裴蜀定理说明的东西。
对于一个二元不定方程 \(ax+by=c\)，该方程的充要条件是 \((a,b)|c\)
顺便再提一下逆元存在的充要条件：
如果 \(a\) 模 \(m\) 的逆元存在，则一定满足 \((a,m)=1\)，即 \(a,m\) 互质
而扩欧能够做的是找到一个 \(ax+by=(a,b)\) 的整数解。
首先，我们根据辗转相除法可以得到 \((a,b)=(b,a\bmod b)\)。
则我们按照递归的方法进去，假设我们找到了这样的一组解，然后我们考虑如何向上更新：
\[bx_2+(a\bmod b)y_2=(b,a\bmod b)=(a,b) \]则可以这样：
\[\because (b,a\bmod b)=(a,b) \]\[\therefore ax_1+by_1=bx_2+(a\bmod b)y_2 \]\[\because a\bmod b=a-\lfloor \frac{a}{b}\rfloor b \]\[\therefore ax_1+by_1=bx_2+(a-\lfloor \frac{a}{b}\rfloor b)y_2 \]\[ax_1+by_1=bx_2+ay_2-\lfloor \frac{a}{b}\rfloor by_2 \]\[\Rightarrow ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2) \]\[\therefore x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2 \]那我们如果要求 \(a\) 的逆元的话只需要求 \(ax+my=(a,m)=1\)，之后再将 \(x\) 取到最小自然数解即可。
扩欧的好处是它不需要满足给定的模数一定是质数的条件，在某些题目中如果多次给出模数且没有保证是质数的话那么它就有优势。可是它的时间复杂度还是 \(O(\log{n})\)。
如果某些毒瘤题目的时间要求卡的特别死的话，且要求大量的求逆元，同时模数的范围还不大的话就可以使用下面的方法。
线性求逆元
对于某些模数不大但要大量求逆元的题目，我们可以考虑 \(O(n)\) 预处理出所有的逆元，之后 \(O(1)\) 查询。
首先 \(1^{-1}\equiv 1\pmod{m}\)。即 \(1\) 的逆元是它本身。
之后我们设 \(m=kx+b\)，也就是我们要求 \(x\) 的逆元。
则 \(kx+b\equiv 0\pmod{m}\)
之后我们两边同乘 \(x^{-1}b^{-1}\)
然后可以往下推：
\[kb^{-1}+x^{-1}\equiv 0\pmod{m} \]\[x^{-1}\equiv -kb^{-1}\pmod{m} \]\[\because k=\lfloor \frac{n}{x}\rfloor,b=（n\bmod x） \]\[\therefore x^{-1}\equiv -\lfloor \frac{n}{x}\rfloor\cdot(n\bmod x)^{-1} \]然后我们保存下 \(inv\) 数组，之后因为 \(n\bmod x<x\)，所以 \((n\bmod x)^{-1}\) 在之前求过，所以可以 \(O(m)\) 预处理。但是这种的问题就是如果 \(m\) 很大，就不太好办了。
卢卡斯定理/Lucas 定理
直接结论：
设 \(l_n^m=C_n^m\bmod p\)，\(C_n^m\) 为组合数 \(\frac{n!}{m!(n-m)!}\)，\(p\) 为质数。
则有：
\[l_n^m=C_{n\bmod p}^{m\bmod p}\times l_{\frac{n}{p}}^{\frac{m}{p}} \]数论函数与积性函数
一个定义整数集合上的函数叫做数论函数。
对于一个函数 \(f(n)\)，如果 \(f(a)f(b)=f(ab)\)，则称 \(f(n)\) 是积性函数。
我们怎么判断一个函数是不是积性函数呢？根据算数基本定理一个大于 \(1\) 的正整数 \(n\) 都可以表示成 \(p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}\)，其中 \(\alpha_i\) 是正整数，\(p_i\) 是质数。所以一个函数 \(f(n)\) 是积性函数的充要条件为 \(f(1)=1\) 且 \(f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})\cdots f(p_k^{\alpha_k})\)
下面给出一些常用的积性函数：
- 常数函数\(1(n)=1\)
- 恒等函数 \(id(n)=n\)
- 单位函数 \(\varepsilon(n)=[n=1]\)
- 欧拉函数 \(\varphi(n)=n\prod\limits_{c|n}(1-\frac{1}{c})\) 或 \(\varphi(n)=\sum\limits_{i=1}^{n}[(i,n)=1]\)
- 因子函数 \(d(n)=\prod\limits_{i=1}^k(a_i+1),a_i为 n 的质因数分解后 p_i 的指数\)
- 除数函数（因数和） \(\sigma(n)=\prod\limits_{c|n} c\)
- 莫比乌斯函数 \(\mu(n)=\begin{cases}1\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space n=1\\(-1)^k \space\space\space\space\space\space\space\space n=p_1\times p_2\cdots \times p_k\\\end{cases}\)
另外，积性函数都可以通过线性筛来求，只需要求出定义中质数的情况，与是否包含最小质因子的两种情况进行分类讨论即可。
莫比乌斯函数的特殊性质
\[\sum\limits_{c|n} \mu(c)=\varepsilon(n) \]欧拉函数的特殊性质
\[\sum\limits_{c|n} \varphi(c)=n \]【证明】
我们首先来考虑 \(\varphi(n)\) 的线性筛方法。对于一个质数 \(p\)，显然 \(\varphi(p)=p-1\)
而对于 \(kp\) 与它不互质的数是 \(1,p,2p\cdots kp\)，一共 \(k\) 个，所以 \(\varphi(kp)=kp-k=k(p-1)\)。之后考虑 \(\varphi(p^k)\)，由上一条得 \(\varphi(p^k)=p^{k-1}(p-1)=p^k-p^{k-1}\)。
然后我们思考 \(\sum\limits_{c|p^k}\varphi(c)\)，显然 \(c\) 的取值只有 \(1,p,p^2\cdots p^k\)，所以 \(\sum\limits_{c|p^k}\varphi(c)=(\sum\limits_{i=1}^k \varphi(p^i))+1=(\sum\limits_{i=1}^k (p^i-p^{i-1}))+1=p^k-p^{k-1}+p^{k-1}-p^{k-2}+\cdots-p^1+p^1-p^0+1=p^k\)。之后因为积性函数的性质 \(\varphi(ab)=\varphi(a)\varphi(b)\),所以根据算数基本定理的话 \(\sum\limits_{c|n} \varphi(c)=\prod\limits_{i=1}^k \sum\limits_{c|p^i}\varphi(c)=n\)。
狄利克雷卷积
这个东西是一种定义在数论函数中的一种二元计算。对于两个函数 \(f(n)\) 与 \(g(n)\)，它们的狄利克雷卷积是这样定义的：
\[(f*g)(n):= \sum\limits_{c|n} f(c)g(\frac{n}{c}) \]显然这个东西满足交换律和结合律，当然它也有另一种表达方法：
\[(f*g)(n):=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^n f(x)g(y)[xy=n] \]特别的，\(\varepsilon(n)\) 是狄利克雷卷积的单位元，即对于所有 \(f(n)\)，都有 \(\varepsilon*f=f\)
莫比乌斯反演
对于两个数论函数 \(f(n),g(n)\)，如果 \(f(n)=\sum\limits_{c|n} g(c)\)，则有 \(g(n)=f*\mu=\sum\limits_{c|n} f(c)\mu(\frac{n}{c})\)。
标签：专题,frac,函数,limits,space,sum,varphi,笔记,集训 From： https://www.cnblogs.com/tanghg/p/18021742/-math2024_2【证明】首先根据上面莫比乌斯函数的性质，\(\varepsilon=1*\mu\),同时 \(f=g*1\)，则有 \(g=g*e=g*(1*\mu)=g*1*\mu=(g*1)*\mu=f*\mu\)，即 \(g(n)=f*\mu=\sum\limits_{c|n} f(c)\mu(\frac{n}{c})\)