-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
逆元.html
32 lines (32 loc) · 1.94 KB
/
逆元.html
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
<title>逆元</title>
<p>
環$R$の要素$a \in R$に対し、$a b = 1$となるような要素$b$を$a$の逆元(inverse)と呼ぶ。
逆元は存在するなら一意である。そこで、逆元の存在する要素に対しては$a^{-1}$として逆元を表すことにする。
逆元が存在する要素を"unit"と呼ぶ。unitのみを集めたものに対して掛け算を演算とするとそれは群になり、これをを$R^*$として表す。
</p>
<h3>剰余環の場合</h3>
<p>
剰余環$R = \mathbb{Z}/m\mathbb{Z}$の要素$a \in R$がunitであるのは、$\gcd(a, m) = 1$であることと同値である。
そのような要素に対しては、拡張ユークリッドの互除法を用いて逆元を求めることができる。
</p>
<h4>${\rm mod}\ p^q$上の場合</h4>
<p>
ニュートン法(Hansel listing)を用いれば拡張ユークリッドの互除法を使うより高速に逆元を求められる。
特に、${\rm mod}\ 2^k$上の場合は重要である。
</p>
<h3>多項式の剰余環の場合</h3>
<p>
多項式の場合でも整数の場合と同じように拡張ユークリッドの互除法で逆元を求められる。
</p>
<h3>formal power series上の場合</h3>
<p>
<a href='http://yukicoder.me/wiki/polynomial_techniques'>多項式を使うテクニックたち</a>参照。
</p>
<h3>多数の逆元を一度に求める</h3>
<p>
長さ$N$の配列$A$に対して、それぞれの要素に対する逆元を全て求めたい。
このとき、1つずつ逆元を求めなくても、逆元を1回だけ計算すれば全ての逆元を求められる。
まず、$p[k] = \displaystyle \prod_{i=0}^{k-1} A[i]$とprefix productを求める。
次に、$p[N]^{-1}$を(普通に)求める。すると、$i < N$に対して$p[i]^{-1} = p[i+1]^{-1} A[i]$として、prefix productの逆元を全て求められる。
最後に、$A[i]^{-1} = p[i+1]^{-1} p[i]$とすれば$A$の全ての逆元を求めることができた。
</p>