企业官网建设流程全解析

南京做网站南京乐识好,宁海关键词优化怎么优化,企业网站意思,tv网站建设线性算法 用于求一连串数字对于一个modp的逆元。洛谷P3811 只能用这种方法#xff0c;别的算法都比这些要求一串要慢。 首先我们有一个,1−1≡1(modp) 然后设 pk∗ir,(1rip) 也就是 k 是 p/i 的商#xff0c;r 是余数 。 再将这个式子放到(modp)意义下就会得…线性算法用于求一连串数字对于一个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;