核心内容摘要
【概念板块和行业板块】
线性算法用于求一连串数字对于一个modp的逆元。
洛谷P3811只能用这种方法别的算法都比这些要求一串要慢。
首先我们有一个,1−1≡1(modp)然后设 pk∗ir,(1rip) 也就是 k 是 p/i 的商r 是余数 。
再将这个式子放到(modp)意义下就会得到k∗ir≡0(modp)然后乘上i−1,r−1就可以得到:k∗r−1i−1≡0(modp)i−1≡−k∗r−1(modp)i−1≡−⌊ip⌋∗(pmodi)−1(modp)于是我们就可以从前面推出当前的逆元了。
代码也很短inv[1] 1; for(int i 2; i p; i) inv[i] (p - p / i) * inv[p % i] % p;