快速幂取模_C++

2018-06-17 23:57:03来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

一、题目背景

  已知底数a,指数b,取模值mo

  求ans = a% mo


 

二、朴素算法(已知可跳过)

  ans = 1,循环从 i 到 b ,每次将 ans = ans * a % mo

  时间复杂度O(b)  

 1 void power(int a,int b,int mo)
 2 {
 3     int i;
 4     ans=1;
 5     for (i=1;i<=b;i++)
 6     {
 7         ans*=a;
 8         ans%=mo;
 9     }
10 }

 


 

三、快速幂

   先讨论无需取模的

  当b为偶数时:ab=a(b/2)*2=(a2)b/2

  当b为奇数时:ab=a*ab-1=a*(a2)(b-1)/2

  如   28=(224         27=2*(22)3

  所以,我们可以如此迭代下去

  210=(22)5=(22)*[(22)2]2

   ①       ②              ③

  指数为10 是一个偶数,则底数2平方,指数变为一半 [ ①→② ]

  指数为5 是一个奇数,则先将底数提出作为系数(22),此时指数为4 是一个偶数,则底数22再平方,指数再变为一半 [ ②→③ ]

  归纳总结得到:

        当指数大于1时,若为 偶数 则将指数除以2,底数平方

                                   若为 奇数 则先提出一个为底数的系数(可直接把该系数乘进ans中),所以指数减1,然后再按照 偶数 的办法做

  不断迭代下去,当指数为1时,则直接得出答案

  最后只要将每次相乘时取模即可,时间复杂度O(log2b)

 

 1 inline int mi(int a,int b)
 2 {
 3     int ans=1;
 4     a%=mo;
 5     while (b)
 6     {
 7         if (b&1) ans=ans*a%mo;
 8         b>>=1;
 9         a=a*a%mo;
10     }
11     return ans;
12 }

 

  (代码更新时间2016年11月7日17:20:54)

 

 

版权所有,转载请联系作者,违者必究

QQ:740929894

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:TCP通信三次握手的过程

下一篇:377. Combination Sum IV