乘法逆元

讲一下为什么要学逆元，对于我们平常遇见的

(a - b) % p = a % p - b % p;

(a + b) % p = a % p + b % p;加减法都是没问题的，都很常见

(a * b) % p = (a % p) * (b % p);乘法我们也通常会遇见

但是除法呢，好像我们一直没有遇见过，那当我们遇见的时候，也可以这样取模吗

既然提出来了，显然不是的

(a / b) % p != (a % p) / (b % p);

所以我们就要学逆元，因为当我们(a / b)难以计数取模或有可能暴精度的情况下，就需要我们给他转换成为乘法

这里讲三种方法

1、拓展欧几里得

作为求逆元最常见的方法，但可能不是最常用的，学到后面就知道为什么了

typedef long long ll;
void Exgcd(ll a, ll p, ll &x, ll &y)
{
    if (!p)
        x = 1, y = 0;
    else
    {
        Exgcd(p, a % p, y, x);
        y -= a / p * x;
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    ll a, p; //a模p
    ll x, y; //求出来的x就是a在模p下的逆元，y用来辅助
    
    scanf("%lld%lld", &a, &p);
    Exgcd(a, p, x, y);
    x = (x % p + p) % p;
    printf("%lld\n", x);
    return 0;
}

这里可以单独求出了每个数对模p的逆元，并且对p没有限制（为什么说这句话，因为第二种方法有限制）

2、费马小定理

这里对一个数求逆元比较快，也是比较常用的，需要用到快速幂，并且对模p是有限制

一定要记得对p有限制，p一定要是素数

一定要记得对p有限制，p一定要是素数

一定要记得对p有限制，p一定要是素数

我以前看到别人用这个去求任何模数，求求了，看傻了都

代码比较简洁，只需要快速幂

a在模p的意义下的逆元，就是a的p-2次方

ll ksm(ll a, ll b, ll p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    ll a, p;
    scanf("%lld%lld", &a, &p);
    ll x = ksm(a, p - 2, p);
    printf("%lld\n", x);

    return 0;
}

3、线性求逆元

这个也比较常用，是用来求连续的一段的逆元

inv[i]等于i在模p意义下的逆元

代码比较简洁

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    ll a, p;
    scanf("%lld%lld", &a, &p);
    inv[1] = 1;
    for(int i = 2; i < n; ++ i)
        inv[i] = (p - p / i) * inv[p % i] % p;
    for (int i = 1;i <= n;i ++)
        printf("%d ", inv[i]);
    return 0;
}