Multiplicative inverse

发表于 | 更新于
本文字数： 2k | 阅读时长 ≈ 2 分钟

$linear$ $inverse$ $element$

$Descirption$

给出 $k$ ，求它的逆元。

$Solution$

设
$$
a \times k + b = p,{b \times inv[b]}\equiv1\pmod p
$$
变式，得
$$
b = p - a \times k,{(p - a \times k) \times inv[b]}\equiv1\pmod p
$$

拆括号，得
$$
{p \times inv[b] - a \times k \times inv[b]}\equiv1\pmod p
$$
即
$$
{-a \times k \times inv[b]}\equiv1\pmod p
$$
观察
$$
a \times k + b = p
$$
两边同是对 $k$ 取模，得
$$
b = p \bmod k
$$
故有
$$
a = p \div k
$$
代入原式，得
$$
{-(p / k) \times inv[p \bmod k] \times k}\equiv 1 \pmod p
$$
即
$$
{-(p / k) \times inv[p \bmod k]} \equiv inv[k] \pmod p
$$

也就是
$$
{(p-p / k) \times inv[p \bmod k]} \equiv inv[k] \pmod p
$$

$Code:$

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
#include<bits/stdc++.h>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
//#define mid ( ( l + r ) >> 1 )
#define lowbit(x) ( x & -x )
#define debug(x) cout << "#x = " << x << endl
#define re register
#define For(i, j, k) for(re int i = j; i <= k; i++)
#define foR(i, j, k) for(re int i = j; i >= k; i--)
using namespace std;
typedef long long ll;
const ll N = 200011;
const ll inf = 0x3f3f3f3f3f3f;

ll n, p, f[N];

namespace IO {

    inline ll read() {
        ll x = 0; bool f = 0; char ch = getchar();
        for(; !isdigit( ch ); ch = getchar()) f^=( ch == '-' );
        for(; isdigit( ch ); ch = getchar()) x = ( x << 3 ) + ( x << 1 ) + ( ch ^ 48 );
        return f? -x: x;
    }

    inline void write( ll x ) {
        if( x < 0 ) putchar( '-' ), x = -x;
        if( x > 9 ) write( x / 10 );
        putchar( x % 10 | 48 );
    }

    inline void wln( ll x ) { write( x ); putchar( '\n' ); }

}

using namespace IO;

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    n = read(), p = read(); f[1] = 1;
    For ( i, 2, n ) f[i] = ( p - p / i ) * f[p % i] % p;
    For ( i, 1, n ) wln ( f[i] ); return 0;
}

/*

*/