线性预处理Mod

\[ \ \]\[ \ \] ------------

ll Inv[N]={1,1}; for(int i=2;i<N;i++) Inv[i]=(MOD-MOD/i) * Inv[MOD%i] %MOD

\[ \ \]\[ \ \]

是不是很妙啊

证明我不会

(但是我会背代码qwq)

我们瞄一眼 \(Mod \ Inv\)的定义

\[ a \cdot p \ \equiv \ 1 \ \ \ (mod \ m) \]

对于这条式子

\[ t \cdot i + k \equiv 0 \ (mod \ m) \]

变一下-->>

\[ \frac{1}{i} \equiv - \frac{t}{k} \ (mod \ m) \]

这个就是 $ Inv[i]=-Inv[k]*t $

我们再瞄一眼代码

(是不是很像!)

由于这个\(MOD/i\)它是向下取整的 , 实际上它应该等于

\[ \frac{(MOD-MOD \ mod \ i)} {i} \]

把它带进$ t \cdot i + k   \equiv   0  (mod  m) $

惊人地发现

\[ t = \frac{(MOD-MOD \ mod \ i)} {i}, k = MOD \ mod \ i \]

刚好成立(某一部分抵掉了)

高兴的笑出了声

转载于:https://www.cnblogs.com/chasedeath/p/11259378.html

相关资源：JAVA上百实例源码以及开源项目