次方(快速幂取模)"/>
【算法】求n的m次方(快速幂取模)
题目
求n的m次方,n,m均为自然数。
解析
看似简单的题目,但是要想写的高效还不是那么容易想出来。
实现
unsigned int power(unsigned int a, unsigned int n)
{unsigned int i, s;if (!n) return 1;if(!a) return 0;i=n;s=a;while (i>>=1)//每次移动递增{s*=s;if ((i&n)==i) s*=a;//解决奇偶}return s;
}
以上算法也可说是:快速幂取模算法的一个优化。
方法二,比较好理解点
unsigned long power(unsigned long m, unsigned long n)
{ unsigned long t = 1; while(n > 0){ if(n & 0x01UL == 1) t *= m; m *= m; n >>= 1; }return t;
}
更多推荐
【算法】求n的m次方(快速幂取模)
发布评论