好贷网好贷款

快速幂

发布时间:2016-12-5 2:25:57 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"快速幂",主要涉及到快速幂方面的内容,对于快速幂感兴趣的同学可以参考一下。

快速幂顾名思义,就是快速算某个数的多少次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。 求a的b次方: 把b转换成二进制数,该二进制数第i位的权为  例如        11的二进制是1011       11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1 因此,将a¹¹转化为 ,也就是算的值 快速幂可以用位运算这个强大的工具实现: b and 1 //取b的二进制最末位 b shr 1 //就是去掉b的二进制最末位 有了这个强大的工具,快速幂就好实现了! var a,b,n:int64; function f(a,b,n:int64):int64; var t,y:int64; begin t:=1;y:=a; while b<>0 do begin if (b and 1)=1 then t:=t*y mod n; y:=y*y mod n; { 这里用了一个很强大的技巧,y*y即求出了 a^(2^(i-1)) 不知道这是什么的看原理 } b:=b shr 1; {去掉已经处理过的一位} end; exit(t); end; begin read(a,b,n); {n是模} writeln(f(a,b,n)); end. 常规求幂int pow1( int a, int b ) { int r = 1; while( b-- ) r *= a; return r; } 二分求幂(一般) int pow2( int a, int b ) { int r = 1, base = a; while( b != 0 ) { if( b % 2 ) r *= base; base *= base; b /= 2; } return r; } 快速求幂(位操作) int pow3( int a, int b ) { int r = 1, base = a; while( b != 0 ) { if( b & 1 ) r *= base; base *= base; b >>= 1; } return r; } 快速求幂(更高效率的位运算法) int pow4(int x, int n) { int result; if (n == 0) return 1; else { while ((n & 1) == 0) { n >>= 1; x *= x; } } result = x; n >>= 1; while (n != 0) { x *= x; if ((n & 1) != 0) result *= x; n >>= 1; } return result; }

上一篇:POJ 2186 Popular Cows / 强连通分量
下一篇:电脑访问手机站跳转至电脑站代码

相关文章

关键词: 快速幂

相关评论