首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >小白详细讲解快速幂--杭电oj2035-A^B

小白详细讲解快速幂--杭电oj2035-A^B

作者头像
用户2038589
发布2018-09-06 11:37:44
5100
发布2018-09-06 11:37:44
举报
文章被收录于专栏:青青天空树青青天空树

Problem Description

求A^B的最后三位数表示的整数。 说明:A^B的含义是“A的B次方”

 Input

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

 Output

对于每个测试实例,请输出A^B的最后三位表示的整数,每个输出占一行。

  简单的说这题就是要求高次幂,有两种方法可以实现。

  第一总比较土鳖,每次乘完对1000取余也可以过。

  我要讲的是第二种听起来很高大上的方法——快速幂。为什么叫快速幂呢?因为用它求幂非常快,对于x^n,复杂度为O(logn),是不是很吊!快速幂的原理是把幂分解,把一个很大的幂分解成较小的几部分。例如:

11的二进制是1011

11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1

因此,我们将a¹¹转化为 

即把n化为2进制数,每个为1的位都是较小的一部分。这样可以用一个循环来解决。下面是快速幂的非递归代码,暂时忽略max

int cal(int x, int n, int max){

  int sum = 1;    //最后输出的结果   while (n > 0){   //当幂降为0是结束   if (n & 1)      //位运算,&是按位与,当两边都为1,表达式为1,这个是用来判断二进制数最后一位是否为1,这里n是以二进制的形式比较的

    sum = sum*x%max;//如果为1,sum就要乘x^i,i为该位在二进制数中的位置   n >>= 1;      //>>为位运算符,右移一位,即去掉已经计算过的部分   x = x*x%max;    //用来标记记录x^2^i,循环i次即去掉了i位,当第i+1位为1时,sum就要乘x^2^i;   }   return sum;//循环结束返回结果。 }

  现在来讲max的作用,用来把数变小的,我们可以想象如果是很大的数的很高次方,乘几次后数据非常大无法用任何一个基本数据类型表示,而且这也是不必要的,通常我们只需要知道最后若干位的值,这就可以用到取余了,余数的幂和原数的幂在余数的位数上是相同的,所以每次进行乘法运算后都要取余,当然如果数据很小也可以不用取余。

  好了,感觉我已经讲的很详细了!!真的是尽力了。。。

下面贴上上面那题的代码

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int cal(int x, int n, int max){
 5     int sum = 1;
 6     while (n > 0){
 7         if (n & 1)
 8             sum = sum*x%max;
 9         n >>= 1;
10         x = x*x%max;
11     }
12     return sum;
13 }
14 int main(){
15     int x, n;
16     while ((cin >> x >> n) && (x || n)){
17         cout << cal(x, n, 1000) << endl;
18     }
19     return 0;
20 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-11-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档