Function nekolib::math::mod_recip_table_prime

pub fn mod_recip_table_prime(n: u64, m: u64) -> Vec<u64>

素数 $m$ を法とした逆元のテーブル。

$\gdef\recip#1#2{#1_{(#2)}^{-1}}$ 以下、$i^{-1}\bmod j$ を $\recip{i}{j}$ と書く。

次で定められる \(a = (a_0, a_1, \dots, a_n)\) を返す。 \[ a_i = \begin{cases} \recip{i}{m}, & \text{if }\recip{i}{m}\text{ exists}; \\ 0, & \text{otherwise}. \end{cases} \] Note: $\recip{i}{m}\ne 0$。

Idea

次のことが成り立つ：

• $\recip{0}{m}$ は存在しない。
• $\recip{1}{m} = 1$ である。

$\recip{(i+m)}{m} = \recip{i}{m}$ なので、$i\lt m$ について考える。

各 $j$ ($1\le j\lt i$) については $\recip{j}{m}$ が得られているとする。ただし、$m$ が素数なので、これらは常に存在する。

$m = q\cdot i+r$ ($0\le r\lt i$) とおき、$\recip{i}{m}$ を辺々掛けると $$ \begin{aligned} m\cdot\recip{i}{m} &= q\cdot i\cdot\recip{i}{m} + r\cdot\recip{i}{m} \\ 0 &\equiv q + r\cdot\recip{i}{m} \pmod{m}. \end{aligned} $$ よって、 $$ \recip{i}{m} \equiv -q\cdot\recip{r}{m} \pmod{m}. $$ $q\gt 0$ と $\recip{r}{m}\gt 0$ であることから、 $$ \recip{i}{m} = m - (q\cdot\recip{r}{m} \bmod m) $$ となる。

$r\lt i$ より $\recip{r}{m}$ は既に得られているため、$\recip{i}{m}$ が順次 $O(1)$ time で求まる。

Notes

一般のケースでは $\gcd(r, m)=\gcd(i, m)$ とは限らないので注意。 たとえば、$\recip{3}{8}$ を求める際、$8 = 3\cdot 2 + 2$ なので $\recip{2}{8}$ が必要になるが、これは存在しない。

一般のケースで必要になる場合は、線形篩を用いる方法がある。See: LinearSieve::recips

Complexity

$O(n)$ time。

Examples

use nekolib::math::mod_recip_table_prime;

assert_eq!(mod_recip_table_prime(2, 3), [0, 1, 2]);
assert_eq!(mod_recip_table_prime(4, 5), [0, 1, 3, 2, 4]);
assert_eq!(mod_recip_table_prime(9, 5), [0, 1, 3, 2, 4].repeat(2));