费马小定理，快速幂

张开发
• 2026/4/12 0:03:17 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

费马小定理，快速幂
今天显示延续了昨天的背包问题先是写了一题背包问题后面就写费马定理加快速幂。费马小定理证明如果一个数p是质数并且a不是p的倍数那么一定有a^p-11mod p);那么自然有a^(p-2)a^-1(mod p)(对于逆元a*(a^-1)1)这可以求逆元以及在除法取模上也有应用而怎么算a^(p-2)呢那就可以通过快速幂了快速幂利用指数的二进制去算因为不管a的几次方相乘最后都是那些指数相加而已那么这时候就可以把指数对应的二进制的每一位对应的十进制写在a的次方上。如果指数1为真即为奇数就让a*res然后a进行平方运算b除以二。这样把从直接算的O(n)优化到了O(logn)

更多文章