八月总结复习

标签：总结 lfloor 复习 inv 八月 rfloor pmodn mod equiv

20240806

kmp
manacher
ac自动机

20240806

线性求逆元
假设我们求取\(n\)关于质数\(p\)的逆元，即求取\(n^{-1}\)

我们设\(a= \lfloor p/n \rfloor , b=p\mod n\)。则有

$a*n+b\equiv 0 (mod\ p) $

移项可得:

\[a*b\equiv-b(mod\ p) \]

\[-a/b\equiv n^{-1}(mod\ p) \]

即:

\[n^{-1}\equiv -a/b (mod\ p) \]

\[n^{-1}\equiv \lfloor -p/n \rfloor /pmodn(mod\ p) \]

\[n^{-1}\equiv-\lfloor p/n \rfloor \cdot (pmodn)^{-1}(mod\ p) \]

所以:

\[n^{-1}\equiv(p-\lfloor p/n \rfloor)\cdot(pmodn)^{-1}(mod\ p) \]

code:

inv[0]=inv[1]=1;
for(int i=2;i<=n;i++){
    inv[i]=(-p/i+p)*inv[p%i]%p;
}

标签：总结,lfloor,复习,inv,八月,rfloor,pmodn,mod,equiv
From： https://www.cnblogs.com/oberzhang/p/18345910