乘法逆元

定义：

如果一个线性同余方程$ax$≡ $1$($mod$ $b$)，则$x$称为$a$ $mod$ $b$的逆元，记作$a^{-1}$。

求逆元的常见方法及其模板

• 扩展欧几里得法：

void exgcd(int a, int b)
{
        if (!b)
        {
                x = 1;
                y = 0;
                return;
        }
        exgcd(b, a % b);
        int t = x;
        x = y, y = t - a / b * y;
}

• 快速幂法：

int qpow(int a, int n)
{
        ll res = 1;
        while (n)
        {
                if (n & 1)
                        res = (res % mod * a % mod) % mod;
                a = (a % mod * a % mod) % mod;
                n >>= 1;
        }
        return res % mod;
}
// n = mod - 2

• 线性递推法：

int mod(int a, int p)
{
        return (a % p + p) % p;
}
int inv(int a, int p)
{
        if (Inv[a])
                return Inv[a];
        Inv[a] = mod(-p / a * inv(p % a, p), p);
        return Inv[a];
}

相关题目分析:

洛谷p3811

原题链接：https://www.luogu.com.cn/problem/P3811

思路分析：

• 模板题

代码如下：

/* 
扩展欧几里得算法
*/
/*
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int p;
int x, y;
void exgcd(int a, int b)
{
        if (!b)
        {
                x = 1;
                y = 0;
                return;
        }
        exgcd(b, a % b);
        int t = x;
        x = y, y = t - a / b * y;
}
void write(int x)
{
        if (x > 9)
                write(x / 10);
        putchar(x % 10 ^ 48);
}
int main()
{
        int n;
        scanf("%d %d", &n, &p);
        for (int i = 1; i <= n; i++)
        {
                exgcd(i, p);
                write((x % p + p) % p);
                putchar('n');
        }
        return 0;
}
*/
/* 
费马小定理
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p;
ll qpow(ll a, ll n, ll p)
{
        ll res = 1;
        while (n)
        {
                if (n & 1)
                        res = (res % p * a % p) % p;
                a = (a % p * a % p) % p;
                n >>= 1;
        }
        return res % p;
}
ll inv(ll a, ll p)
{
        return qpow(a, p - 2, p);
}
void write(int x)
{
        if (x > 9)
                write(x / 10);
        putchar(x % 10 ^ 48);
}
int main()
{
        ll n;
        cin >> n >> p;
        for (int i = 1; i <= n; i++)
        {
                write(inv(i, p));
                putchar('n');
        }
        return 0;
}
/*
线性递推
*/
/*
#include <bits/stdc++.h>
#define ll long long
const int maxn = 3e6 + 10;
using namespace std;
ll p;
ll Inv[maxn];
void write(int x)
{
        if (x > 9)
                write(x / 10);
        putchar(x % 10 ^ 48);
}
ll mod(ll a, ll p)
{
        return (a % p + p) % p;
}
ll inv(ll a, ll p)
{
        if (Inv[a])
                return Inv[a];
        Inv[a] = mod(-p / a * inv(p % a, p), p);
        return Inv[a];
}
int main()
{
        Inv[0] = 0;
        Inv[1] = 1;
        ll n;
        cin >> n >> p;
        for (int i = 1; i <= n; i++)
        {
                write(inv(i, p));
                putchar('n');
        }
        return 0;
}
*/

洛谷p5431

思路分析：

• 由于要对答案取模，所以要将除法变为乘法，即求逆元

• 其次，为了减少时间复杂度，我们可以递推出一个公式如下：

• 得到答案

代码如下：

#include <bits/stdc++.h>
#define ll long long
const ll N = 5e6 + 10;
ll read()
{
        int x = 0, flag = 1;
        char c;
        while ((c = getchar()) < '0' || c > '9')
                if (c == '-')
                        flag = -1;
        while (c >= '0' && c <= '9')
                x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
        return x * flag;
}

inline ll qpow(ll a, ll n, ll p)
{
        ll res = 1;
        while (n)
        {
                if (n & 1)
                        res = (res % p * a % p) % p;
                a = (a % p * a % p) % p;
                n >>= 1;
        }
        return res % p;
}

ll n, p, k, a[N], s[N], invs[N], ans;

int main()
{
        n = read(), p = read(), k = read();
        s[0] = 1;
        for (ll i = 1; i <= n; ++i)
                a[i] = read(), s[i] = s[i - 1] * a[i] % p;
        invs[n] = qpow(s[n], p - 2, p);
        for (ll i = n - 1; i >= 0; --i)
                invs[i] = invs[i + 1] * a[i + 1] % p;
        for (ll i = n; i; --i)
                ans = (invs[i] * s[i - 1] % p + ans) * k % p;
        printf("%d", ans);
        return 0;
}

洛谷p1082

思路分析

• 要求解$ax=1$ ($mod$ $b$)中的$x$，实际上我们只需要求$a$在模$b$意义下的逆元即可
• 此题我们采用扩展欧几里得进行求解，因为模数不一定满足费马小定理

代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int p;
int x, y;
void exgcd(int a, int b)
{
        if (!b)
        {
                x = 1;
                y = 0;
                return;
        }
        exgcd(b, a % b);
        int t = x;
        x = y, y = t - a / b * y;
}
void write(int x)
{
        if (x > 9)
                write(x / 10);
        putchar(x % 10 ^ 48);
}
int main()
{
        int n;
        scanf("%d %d", &n, &p);
        exgcd(n, p);
        write((x % p + p) % p);
        putchar('n');
        return 0;
}

最后

以上就是爱听歌苗条为你收集整理的乘法逆元及简单利用乘法逆元的全部内容，希望文章能够帮你解决乘法逆元及简单利用乘法逆元所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。