主要还是模运算下乘法运算的逆元，下文中逆元都会带有下标 \(inv\)。

如果一个线性同余方程 \(ax\equiv 1\pmod{b}\)，则称 \(x\) 为 \(a\bmod b\) 的逆元，记作 \(a^{-1}\)。——————OI Wiki

\(a \equiv b \pmod{m}\)

老朋友了，表示 \(a\bmod m=b\mod m\)。

然后看一下这个：\(\frac{a}{b} \equiv x\pmod{p}\).

模意义下的除法在大多数时候都不适用。

当题目中要求对答案取模，但我们又不得不使用一般的除法的时候，就需要用逆元的乘法来代替除法。

根据逆元的定义得：

\((a\times b_{inv}) \equiv x \pmod{p}\);

左右两边同乘 \(b\),移项得：

\(\left\{\begin{matrix}(b\times a\times b_{inv})\equiv x\times b \pmod{p}\\a\equiv b\times x \pmod{p}\end{matrix}\right.\)

上减下得：

\(a\times(b\times b_{inv}-1)\equiv 0 \pmod{p}\)

移项得：

\(b\times b_{inv}-1\equiv 0 \pmod{p}\);

两边同时加一得：

$ b\times b_{inv}\equiv 1\pmod{p}$；

设一个正整数 \(k\) ；

两边同时加 \(k\times p\) 得；

$ b\times b_{inv}+k\times p\equiv 1+k\times p\pmod{p}$；

因为 \((k\times p )\bmod p=0\);

所以：$ b\times b_{inv}+k\times p\equiv 1\pmod{p}$；

根据我们的扩展欧几里得可以得知：当知道 \(a,b\) 的值的时候是可以求出 \(a\times x+b\times y=gcd(a,b)\) 中的 \(x,y\) 的值。当然前提是 \(b,p\) 互质的时候上面的柿子就可以得出：

\(b\times b_{inv}+k\times p= 1\)；

知道 \(b,p\) 就可以愉快的求 \(b_{inv}\) 啦。

好的到了这一步已经可以有两种解决方式了，一种是用扩展欧几里得来解逆元，另一种是用费马小定理，先来好理解的。

首先回到我们前面推的柿子；

$ b\times b_{inv}\equiv 1\pmod{p}$；

好的现在我们可以知道当 \(p\) 为质数时：

\(a^{p}\equiv a\pmod{p}\);

稍微变换一下得：

\(a^{p-1}\times a\equiv a\pmod{p}\)

因为 \(a\) 是正整数，两边同除 \(a\) 得：

\(a^{p-1}\equiv 1 \pmod{p}\);

根据我们上面得出得柿子一结合就可以得出：

\(\left.\begin{matrix} b\times b_{inv}\equiv 1\pmod{p} \\ b\times b^{p-2}\equiv 1\pmod{p}\end{matrix}\right\}\Rightarrow b_{inv}=b^{p-2}\)

所以我们就可以用：

\(a\times b^{p-2} \bmod p\) 来求 $ \frac{a}{b}\bmod p$ 啦。

前面的都太慢了，我们要追求效率。

首先我们有一个 \(1_{inv}\equiv 1\pmod{p}\);

我们设 \(p=k\times i+r\)；

然后放到 \(\pmod{p}\) 意义下就可以得到：

\(k\times i+r\equiv 0\pmod{p}\);

乘上 \(i_{inv},r_{inv}\) 可以得到;

\(k\times r_{inv}+i_{inv}\equiv 0\pmod{p}\)

移项得：

\(i_{inv}\equiv -k\times r_{inv}\pmod{p}\)

把 \(k,r_{inv}\) 用 \(p\) 表示出来就好了。

\(i_{inv}\equiv -\left \lfloor \frac{p}{i} \right \rfloor \times (p\bmod i)_{inv} \pmod{p}\);

贴一下代码：

inv[1] = 1;for(int i = 2; i < p; ++ i)    inv[i] = (p - p / i) * inv[p % i] % p;

数论函数：在数论上，对于定义域为正整数，值域为复数的函数，我们称之为数论函数。

非完全积性函数：对于数论函数 \(f\)，若满足 \(gcd(a,b)=1\) 时，有 \(f(ab)=f(a)\times f(b)\)，则称函数 \(f\) 为积性函数.

完全积性函数：对于数论函数 \(f\)，即使不满足 \(gcd(a,b)=1\)，仍有 \(f(ab)=f(a)\times f(b)\)，则称函数 \(f\) 为完全积性函数.

\(\varphi (n)\)————欧拉函数，计算从一到 \(n\) 与 \(n\) 互质的数的数目。

\(\mu(n)\)————莫比乌斯函数，关于非平方数的质因子数目.

\(\mu(n)=\left\{\begin{matrix} 1 \ \ (n=1) \\ 0\ \ \ \ (n\text{含有1除外的平方因子}) \\ (-1)^{k}\ \ \ \ (k\text{为}n\text{的本质不同质因子个数）} \end{matrix}\right.\)

\(\gcd(n,k)\)————最大公约数函数，当 \(k\) 固定的情况时是积性函数。

\(d(n)\)————\(n\) 的正因子数目。

\(\sigma(n)\)————\(n\) 的正因子之和。

\(\sigma k(n)\)————因子函数，\(n\) 的所有正因子的 \(k\) 次幂之和，当中 \(k\) 可以为任何复数。

\(1(n)\)————不变的函数，定义为 \(1(n)=1\) （完全积性函数）。

\(id(n)\)————单位函数，定义为 \(id(n)=n\) （完全积性函数）。

\(idk(n)\)————幂函数，对于任何复数、实数 \(k\)，定义为 \(idk(n)=n^k\)（完全积性函数）。

\(\xi(n)\)————定义为：若 \(n=1\),\(\xi(n)=1\);若 \(n>1,\xi(n)=0\)。别称为“对于狄利克雷卷积的乘法单位”（完全积性函数）。

\(\lambda(n)\)————刘维尔函数，关于能整除 \(n\) 的质因子的数目.

\(\gamma(n)\)————定义为 \(\gamma(n)=(-1)^{\omega(n)}\),在此加性函数 \(\omega(n)\) 是不同能整除 \(n\) 的质数的数目。

参考资料：OI WIKI，自为风月马前卒的博客，https://www.cnblogs.com/zylAK/p/9569668.html ，b站董晓算法。