数论倒数总结

技术文章 10个月前 完美者
1,470 0

标签:www   ref   mod   blog   欧拉定理   shadow   总结   math   应用   

数论倒数总结

一、原理

求解\(a*x≡1(\mod p)\)中的\(x\)


方法一:扩展欧几里德定理

将方程变为:\(a*x+b*y=1\)即可。


方法二:欧拉定理

\((a,n)=1\),有\(a^{\phi(n)}≡1(\mod n)\)

请注意该方法的使用条件。


方法三:费马小定理

\(a^p≡a(\mod p)\)(\(p\)为质数)

请注意该方法的使用条件。


二、基础应用

  • 求解\(1\)~\(n\)所有数关于\(p\)的数论倒数。

    考虑递推:\(p=k*i+r\),则有:\(k*i+r≡0(\mod p)\),两式同时乘以\(i^{-1}\)\(r^{-1}\),得:\(i^{-1}≡-k*r^{-1}(\mod p)\),线性递推。

  • 求解阶乘的所有数论倒数。

    考虑使用费马小定理求解\(n!^{-1}\),然后有:\(i!^{-1}≡(i+1)^{-1}*(i+1)\)

参考资料:https://www.luogu.com.cn/blog/zjp-shadow/cheng-fa-ni-yuan

数论倒数总结

标签:www   ref   mod   blog   欧拉定理   shadow   总结   math   应用   

原文地址:https://www.cnblogs.com/zach20040914/p/14128327.html

版权声明:完美者 发表于 2020-12-18 12:32:09。
转载请注明:数论倒数总结 | 完美导航

暂无评论

暂无评论...