求a的b次方、a的b次方对m取模

约定不等于承诺〃 2022-08-25 05:28 183阅读 0赞

### [求a的b次方、a的b次方对m取模][a_b_a_b_m] ###

*  快速计算乘方的算法，求a的b次方

> 如计算2^13，则传统做法需要进行12次乘法，但是可以优化：  
> 把2\*2的结果保存起来看看，是不是成了：4\*4\*4\*4\*4\*4\*2  
> 再把4\*4的结果保存起来：16\*16\*16\*2  
> 一共5次运算，分别是2\*2、4\*4和16\*16\*16\*2  
>   
> 这样分析，我们算法因该是只需要计算一半都不到的乘法了。  
> 为了讲清这个算法，再举一个例子2^7：2\*2\*2\*2\*2\*2\*2  
> 两两分开：(2\*2)\*(2\*2)\*(2\*2)\*2  
> 如果用2\*2来计算，那么指数就可以除以2了，不过剩了一个，稍后再单独乘上它。  
> 再次两两分开，指数除以2： ((2\*2)\*(2\*2))\*(2\*2)\*2  
> 实际上最后一个括号里的2 \* 2是这回又剩下的，那么，稍后再单独乘上它  
> 现在指数已经为1了，可以计算最终结果了：16\*4\*2=128  
> 
> 
> **\[cpp\]**  [view plain][] [copy][view plain]
> 
> 1.   **long**my\_power(**long**a,**long**b)
> 2.  \{
> 3.  **long**r=1; //用来计算"剩下的"乘积 
> 4.  **if**(b==0)
> 5.  **return**1;
> 6.  **if**(b<0)
> 7.  **return**0;
> 8.  **while**(b>1)
> 9.  \{ // 一直计算到指数小于或等于1 
> 10. **if**((b&1)!=0) //判断p是否奇数，偶数的最低位必为0
> 11. r\*=a; // 若r为奇数，则把"剩下的"乘起来
> 12. a \*=a;// 主体乘方
> 13. b/=2;// 指数除以2
> 14. \}
> 15. **return**r\*a;// 最后把主体和“剩下的”乘起来作为结果
> 16. \}
> 
>   
>   
>

*  求x的y次方对z取模(x^y)mod z：蒙格马利快速幂模算法

> X^Y可以看作Y个X相乘，即然有积模分解公式，那么我们就可以把Y个X相乘再取模的过程分解开来，比如：(17^25))则可分解为：( ( 17 \* 17 ) % 29 \* ( 17 \* 17 ) % 29 \* ……  
> 
> 
> 如果用上面的代码将这个过程优化，那么我们就得到了著名的蒙格马利快速幂模算法：
> 
> **\[cpp\]**  [view plain][] [copy][view plain]
> 
> 1.   **long**Montgomery(**long**a,**long**b,**long**m)
> 2.  \{
> 3.  **long**r=1;
> 4.  a %=m;
> 5.  **while**(b>1)
> 6.  \{
> 7.  **if**((b&1)!=0)
> 8.  r = (r\*a)%m;
> 9.  a = (a\*a)%m;
> 10. b/=2;
> 11. \}
> 12. **return**(r\*a)%m;
> 13. \}

[a_b_a_b_m]: http://blog.csdn.net/chenqiumiao/article/details/6750517
[view plain]: http://blog.csdn.net/chenqiumiao/article/details/6750517#