[关闭]
@xingxing 2017-01-15T17:07:37.000000Z 字数 1244 阅读 1192

快速幂

快速幂


快速计算某个数的多少次幂,时间复杂度O(logn)
own 理解:通过把十进制幂不断除以2变为2进制位(划分幂,使得幂划分部分减少),比如(11)10=(1011)2,这样可以把高次幂的计算时间复杂度由O(n)降为O(logn)。然后由

这里用了一个很强大的技巧,y*y即求出了a^(2^(i-1))
a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
而且一般情况下a*b mod c =(a mod c)*(b mod c) mod c

可以知道,通过比本位低一位的权相乘可以得到本位的权,即2^0,2^1,2^2,……,2^n,之后就要判断幂是否能划分成该位的权。可以通过二进制的最低位来判断,现在每一位都对应一个权,在不断右移二进制位时,如果该位为0即表明幂的划分中没有该位的权,如果为1,则在最后的答案上乘上该位的权,直到二进制数为0.在规定了模值的情况下,应该知道,相乘的过程是可能会溢出的,所以要根据乘数的范围,定义一个恰当的类型(一般,long long int),而且赋值也可能会溢出,所以最后取模。
不是

  1. int n = a * a;
  2. n = n % 1000;

而应该是

  1. int n = a * a % 1000;

(一)快速幂位操作

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. //位操作
  5. const int MOD = 100000;
  6. long long int pow4(long long int a,long long int b)
  7. {
  8. long long int r = 1;
  9. long long int base;
  10. base = a % MOD;
  11. while(b != 0)
  12. {
  13. if(b & 1) r = (r * base) % MOD;
  14. base = (base * base) % MOD;
  15. //printf("base = %lld\n",base);
  16. b >>= 1;
  17. }
  18. return r;
  19. }
  20. int main()
  21. {
  22. long long int a,b;
  23. while(scanf("%lld%lld",&a,&b) != EOF)
  24. {
  25. printf("%lld的%lld次幂为%lld\n",a,b,pow4(a,b));
  26. }
  27. return 0;
  28. }

(二)快速幂

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. //位操作
  5. const int MOD = 10000000;
  6. long long int PowerMod(long long int a,long long int b)
  7. {
  8. long long int ans = 1;
  9. a = a % MOD;
  10. while(b > 0)
  11. {
  12. if(b % 2 == 1) ans = (ans * a) % MOD;
  13. a = (a * a) % MOD;
  14. b = b / 2;
  15. //printf("a = %lld\n",a);
  16. }
  17. return ans;
  18. }
  19. int main()
  20. {
  21. long long int a,b;
  22. while(scanf("%lld%lld",&a,&b) != EOF)
  23. {
  24. printf("%lld的%lld次幂为%lld\n",a,b,PowerMod(a,b));
  25. }
  26. return 0;
  27. }

百度

博客

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注