Function nekolib::math::mod_recip_table_prime

source · 
pub fn mod_recip_table_prime(n: u64, m: u64) -> Vec<u64>
Expand description

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

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

次で定められる a=(a0,a1,…,an)a = (a_0, a_1, \dots, a_n) を返す。 ai={i(m)−1,if i(m)−1 exists;0,otherwise. a_i = \begin{cases} \recip{i}{m}, & \text{if }\recip{i}{m}\text{ exists}; \\ 0, & \text{otherwise}. \end{cases} Note: i(m)−1≠0\recip{i}{m}\ne 0。

Idea

次のことが成り立つ：

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

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

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

m=q⋅i+rm = q\cdot i+r (0≤r<i0\le r\lt i) とおき、i(m)−1\recip{i}{m} を辺々掛けると m⋅i(m)−1=q⋅i⋅i(m)−1+r⋅i(m)−10≡q+r⋅i(m)−1(modm). \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} よって、 i(m)−1≡−q⋅r(m)−1(modm). \recip{i}{m} \equiv -q\cdot\recip{r}{m} \pmod{m}. q>0q\gt 0 と r(m)−1>0\recip{r}{m}\gt 0 であることから、 i(m)−1=m−(q⋅r(m)−1 mod m) \recip{i}{m} = m - (q\cdot\recip{r}{m} \bmod m) となる。

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

Notes

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

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

Complexity

O(n)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));