逆元

关于求逆元，转自这里：

什么是逆元？如果如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。

我们可以使用扩展欧几里得来求逆元，为什么呢？

ax≡1 (mod p)即ax-yp=1.把y写成+的形式就是ax+py=1，为方便理解下面我们把p写成b就是ax+by=1。就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然后就可以用扩展欧几里得求了。

关于逆元的用途：

做题时如果结果过大一般都会让你模一个数，确保结果不是很大，而这个数一般是1e9+7，而且这个数又是个素数，加减乘与模运算的顺序交换不会影响结果，但是除法不行。有的题目要求结果mod一个大质数，如果原本的结果中有除法，比如除以a,那就可以乘以a的逆元替代。（除一个数等于乘它的倒数，虽然这里的逆元不完全是倒数，但可以这么理解，毕竟乘法逆元就是倒数的扩展）。

求逆元代码如下：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

void exgcd(LL a,LL b,LL& d,LL& x,LL& y)
{
    if(!b) { d = a; x = 1; y = 0; }
    else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}

LL inv(LL a, LL p)
{
    LL d, x, y;
    exgcd(a, p, d, x, y);
    return d == 1 ? (x+p)%p : -1;
}

int main()
{
    LL a,p;
    while(1)
    {
        scanf("%lld %lld",&a,&p);
        printf("%lld
",inv(a,p));
    }
}