乘法逆元求法

八月 05, 2018 3301

数论中的重要内容

注意：本文只讨论模数为质数的情况，因为当模数为合数时，不一定所有数都有逆元

定义

在 \bmod\ p 的意义下，我们把 x 的乘法逆元写作 x^{-1} 。乘法逆元有这样一条性质：

x \times x^{-1} \equiv 1\ (\bmod\ p)

乘法逆元有什么用呢？

模意义下的除法运算！

除法运算对于模运算来说并不是「封闭」的，所以我们可以把除法转化成乘法

费马小定理求法

前置知识：「快速幂」

a^{p-1} \equiv 1 (\bmod\ p)%

经过变形，可得

a \times a^{p-2} \equiv 1(\bmod\ p)

由定义可得， a 的乘法逆元就是 a^{p-2}

这就要用到「快速幂」

1
2
3
4
5
6
7
8
9
10
11
12
13
inline int slowPower(int a, int b, int p) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}

inline int invMod(int x, int p) {
    return slowPower(x, p - 2, p);
}

代码实现

输出1到n的逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    inline long long int getint() {
        long long int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10ll + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(long long int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(long long int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = 5000000 + 10;
    
    long long int n, k, HA, a[MAXN];
    long long int fac[MAXN], invf[MAXN];
    
    long long int SlowPower(long long int a, long long int x) {
        //  a^x mod m
        long long int ret = 1;
        if (x == 1) return a;
        while (x) {
            if (x & 1) ret = ret * a % HA;
            a = a * a % HA;
            x >>= 1;
        }
        return ret;
    }
}

signed main() {
    using namespace Solution;
    using namespace FastIO;
    n = getint(); HA = getint();
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = (fac[i - 1] * i) % HA;
    }
    invf[n] = SlowPower(fac[n], HA - 2);
    for (long long int i = n - 1; i >= 1; --i) {
        invf[i] = (invf[i + 1] * (i + 1)) % HA;
    }
    for (long long int i = 1; i <= n; ++i) {
        printf("%lld\n", (invf[i] * fac[i - 1]) % HA);
    }
    return 0;
}