ACM中大数幂运算，输出结果后几位

我也是ACM初学者，最近为了准备校赛去做了好多工具题，比如说关于贪心问题，果园问题，大数阶乘，大数幂运算等等。现在就关于大数幂运算来探讨下怎么让你的算法又快又准！

 

原题来自：HDU2035(传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2035)；

 

Problem Description

 

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

 

 

Input

 

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

 

 

Output

 

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

 

 

Sample Input

2 3 12 6 6789 10000 0 0

 

 

Sample Output

8 984 1

 

 

Author

 

lcy

 

 

Source

 

ACM程序设计期末考试（2006/06/07）

 

 

 

Recommend

 

lcy   |   We have carefully selected several similar problems for you:  1021 2034 1008 2033 1108

10000^10000次怎么想也是超过了long的存储范围，所以暴力运算pow(10000,10000)求解是根本不行的！而且这道题目的时间限制也是在1S秒，如果你暴力求解时间复杂度O(n*n)，n=10000的时候也肯定是超时的！

 

为了解决溢出问题，我们不能再完全计算后取摸，我们可以在a^b可以看成a*a*a.......(b个a相乘)，我们可以在每两个a相成之后取模，那么第一次我们就可以分成(如果b一直都是偶数)b/2组a*a%1000，然后把每组a*a%1000的值赋值给a，b= b/2；这样在我们有面对的就是a^b模型了。一直迭代下去一直到b==1为止！输出b==1的时候a的值就是所要的结果！这样又解决了时间超时的问题，这种算法的时间复杂度为O(log2(n));

 

刚才我们假设的是b一直是偶数的情况，当时这种情况是极少发生的（当且仅当a = 2^n的时候成立）这个时候我们需要考虑如果b%2 != 0的情况也就是说b是奇数，这说明了在某次运算时候这些a*a*a...必定存在一个落单的a。尽管它是落单的，但是它也在影响着最后的结果。为了解决这个问题，我们可以定义一个变量用来收集所有在计算过程中落单的a;这里我初始化int left = 1;每次有落单的a,left = left *a%1000；这样我们就收集了所有落单的a;

 

好了分析到这里我们用代码说话吧！

#include<iostream>
using namespace std;
int main(){
    int A,B;
    while(cin>>A>>B){
        int left=1;
        int result;
        if(A == 0)break;
        while(B!=2&&B!=1){
            if(B%2==1){
                    B--;
                    left = left*A%1000;
                    A = A*A%1000;
                    B = B/2;
            }else{
                A = A*A%1000;
                B = B/2;
            }
        }
        if(B==2){
            result = A*A%1000;
            result = result*left%1000;
        }else{
            result = A*left%1000;

        }
        cout<<result<<endl;
    }
    return 0;
}