快速幂取模
程序员文章站
2022-07-09 10:26:47
...
快速幂取模的用途:我们可能会遇到指数型的数据取模问题,这个时候如果直接用int或者long long储存,就有可能会超出计算机整数的存储范围,而导致数据出错,所以我们需要用快速幂取模进行计算。这种算法在时间和空间上都做了尽可能的优化,所以学会之后,会觉得非常好用。
快速幂取模的思路:快速幂实现的最基本的理论就是我们离散课上或者数论中学过的一条公式推出的引理。
引理:积的取余等于取余的积的取余。
有关快速幂的具体分析参考博客:https://blog.csdn.net/qq_42815188/article/details/84326228
long long MyPowerMode(long long a,long long b,long long mode)
{
long long ans = 1;
while(b)
{
if(b&1)
ans = (ans*a)%mode;
a = (a*a)%mode;
b>>=1;
}
return ans;
}
上一篇: python RC4加密
下一篇: 快速幂取模