乘法逆元

什么是逆元？

设x是a的倒数，那么 x * a = 1（即x = 1 / a).

设x是a的逆元，那么 x * a % p = 1.

逆元的用处

关于取模运算:

(a + b) % p = (a % p + b % p) % p

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

(a b) % p = (a % p ) ( b % p ) % p

(a / b) % p = （a * （b的逆元））% p

逆元可以将除法取模转为乘法取模

如何求解一个数的逆元？

①费马小定理

给出质数 p ，有一个与 p 互质的数 a （即 gcd(a, p) == 1 )，那么有a ^ (p - 1) % p == 1恒成立

根据这一点得 a 的逆元 x = a ^ (p - 2)

所以求一个数的逆元，要明确它本身和一个与它互质的质数 ,根据快速幂求得

②扩展欧几里得

已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足等式： $ax + by = \gcd(a, b)$ 。

为什么可以用扩展欧几里得求解逆元？

因为a x % p = 1 就是a x - p * y = 1.

把y写成+的形式就是ax+py=1，为方便理解下面我们把p写成b就是ax+by=1。

就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然后就可以用扩展欧几里得求了。

所以求一个数 a 的模 p 逆元，不管p质数与否，只需明确a与p

Code（exgcd扩展欧几里得）

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

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

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

int main()
{
    ll a, p;
    while(cin >> a >>p)
        cout << inv(a, p) <<'\n';
    return 0;
}

例题HDU 1576 A / B

Description

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

Input

数据的第一行是一个T，表示有T组数据。每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

Output

对应每组数据输出(A/B)%9973。

Sample Input

2

1000 53

87 123456789

Sample Output

7922

6060

Code(费马小定理)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 9973;

ll quick_pow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        ll n, b;
        cin >> n >> b;
        cout << (n * quick_pow(b, mod - 2)) % mod << '\n';
    }
    return 0;
}

Code（扩展欧几里得）

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

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

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        ll n, b, x, y, gcd;
        cin >> n >> b;
        exgcd(b, 9973, gcd, x, y);
        x = (x + 9973) % 9973;
        cout << (n * x % 9973) % 9973 << '\n';
    }
    return 0;
}