乘法逆元
我们知道，由于同余的运算只定义在整数集中，而整数集不满足除法封闭，所以同余是不满足同除性的。但是，如果有涉及取模操作的计数类题目当中需要除法运算怎么办，这就需要乘法逆元了。
定义
若整数\\(b,m\\)互质，且\\(b|a\\)，则存在一个整数\\(x\\)，满足\\(\\frac{a}{b}\\equiv ax(mod\\ m)\\)，称\\(x\\)为\\(b\\)在模\\(m\\)意义下的乘法逆元，即为\\(b^{-1}(mod\\ m)\\)。
通常来说，我们会使用另一种方式来表示逆元：
\\[\\frac{a}{b}\\equiv ab^{-1}\\equiv \\frac{a}{b}*b*b^{-1}(mod\\ m)\\]
故对于逆元\\(b^{-1}(mod\\ m)\\)，满足\\(b*b^{-1}\\equiv 1(mod\\ m)\\)。
求解
了解了模意义下乘法逆元的定义和作用，那么我们需要知道如何求解。通常来说，我们有好几种常用的方式，如费马小定理，扩展欧几里得等，接下来我们一一详解。
费马小定理
若\\(p\\)为质数，则对于任意整数\\(a\\)，有\\(a^p\\equiv a(mod\\ p)\\)。
注意到著名的费马小定理和我们的逆元非常像，可以推导一下：
\\[ a^p\\equiv a(mod\\ p) \\\\a^{p-1}\\equiv 1(mod\\ p) \\\\a*a^{p-2}\\equiv 1(mod\\ p) \\]
所以，当模数\\(p\\)为质数时，\\(a^{p-2}\\)就是\\(a\\)在模\\(p\\)意义下的乘法逆元。
\\(a^{p-2}\\)显然是可以用快速幂算的，那么我们就得到了逆元的第一种解决方案，可以求解单独一个数的逆元，时间复杂度为\\(O(log_2p)\\)。
\\(Code:\\)
inline long long power(long long a,long long b,long long p)
{
long long res=1;
while (b)
{
if (1&b)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
inline long long Fermat(long long a,long long p)
{
return power(a,p-2,p);
}欧拉定理
若正整数\\(a,p\\)互质，则\\(a^{ϕ(p)}≡1(mod\\ p)\\)，\\(ϕ(p)\\)为欧拉函数。
费马小定理求逆元的话是要求模数\\(p\\)为质数的，更一般地，如果只能保证\\(a,p\\)互质，那么我们可以用欧拉定理求逆元。
\\[ a^{\\phi(p)}\\equiv 1(mod\\ p) \\\\a*a^{\\phi(p)-1}\\equiv 1(mod\\ p) \\]
那么\\(a^{\\phi(p)-1}\\)就是\\(a\\)在模\\(p\\)意义下的一个乘法逆元。
欧拉函数可以用试除法分解质因数求，那么这就是求解逆元的第二种方法，可以求解单独一个数的逆元，时间复杂度\\(O(\\sqrt p+log_2p)\\)。
\\(Code:\\)
inline long long power(long long a,long long b,long long p)
{
long long res=1;
while (b)
{
if (1&b)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
inline long long phi(long long x)
{
long long ans=x;
for (long long i=2;i*i<=x;i++)
{
if (x%i==0)
{
ans=ans/i*(i-1);
while (x%i==0)x/=i;
}
}
if (x>1)ans=ans/x*(x-1);
return ans;
}
inline long long Eular(long long a,long long p)
{
return power(a,phi(p)-1,p);
}线性同余方程
我们已经知道了只有\\(a,p\\)互质时逆元\\(a^{-1}\\)的求法，但是试除法求解欧拉函数未免有点慢。考虑到我们已经得到了逆元的表达方式，其实我们可以直接通过解线性同余方程的方法入手，求解逆元。
已知逆元\\(a^{-1}(mod\\ p)\\)满足\\(a*a^{-1}\\equiv 1(mod\\ p)\\)，令\\(x=a^{-1}\\)，则\\(ax\\equiv 1(mod\\ p)\\)。
这是一个简单的线性同余方程，设\\(-py=ax-1\\)，则可以将方程改写为\\(ax+py=1\\)，利用扩展欧几里得算法找到解。
这就是求解逆元的第三种方法，以求解单独一个数的逆元，时间复杂度\\(O(log_2a+log_2p)\\)。
\\(Code:\\)
inline long long Exeuclid(long long a,long long &x,long long b,long long &y,long long c)
{
if (!b){x=c/a,y=0;return a;}
else
{
long long p=Exeuclid(b,x,a%b,y,c);
long long x_=x,y_=y;
x=y_,y=x_-a/b*y_;
return p;
}
}
inline long long Euclid(long long a,long long p)
{
long long x_,y_;
Exeuclid(a,x_,p,y_,1);
return (x_+p)%p;
}逆元递推
如果求的是单独一个数的逆元的话，那么以上的算法基本上可以完美解决了。现在，如果需要快速的求解\\(1-n\\)每一个数模\\(p\\)意义下的逆元，我们就需要要到逆元递推了。
引理：\\(x^{-1}=(p-\\frac{p}{x})*(p\\ mod\\ x)^{-1}\\ mod\\ p\\)
证明：
设\\(t=\\lfloor \\frac{p}{x} \\rfloor\\)，\\(k=p\\ mod\\ x\\)，即\\(p=tx+k\\)。
那么显然有\\(tx+k\\equiv 0(mod\\ p)\\)，则\\(-tx\\equiv k(mod\\ p)\\)。
将上式两边同时除以\\(x*k\\)，则\\(-t*k^{-1}\\equiv x^{-1}(mod\\ p)\\)，进而得到\\(x^{-1}=(p-\\frac{p}{x})*(p\\ mod\\ x)^{-1}\\ mod\\ p\\)。
已知\\(1^{-1}=1\\)，那么剩下的递推就行了，可以求解\\(1-n\\)所有数的逆元，时间复杂度\\(O(n)\\)。
\\(Code:\\)
inline long long recursion(int n)
{
inv[1]=1;
for (int i=2;i<=n;i++)
inv[i]=(p-p/i)*inv[p%i]%p;
}逆元递归
当然，利用上述引理，我们也可以直接递归来求解单独一个数的逆元，时间复杂度为\\(O(log_2a)\\)。
\\(Code:\\)
inline long long inv(long long x,long long p)
{
if (x==1)return 1;
else return (p-p/x)*inv(p%x)%p;
}总结
至此，本文已经介绍了\\(5\\)种求乘法逆元的方案，其中每一种方法都有各自的优缺点，希望读者能够灵活运用，选择合适的方法来求解逆元。
