人见人爱A^B

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 62195    Accepted Submission(s): 41223
 

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

典型的快速幂问题，函数写出来就能过，可是我记不清了，再学习一遍快速幂吧。

先看代码：

typedef long long ll;
ll quickpow(ll a, ll n, ll mod)//快速幂计算a^n % mod
{
    ll re = 1;
    while(n)
    {
        if(n & 1)//判断二进制n的最后一位是否为1
            re = (re * a) % mod;
        n >>= 1;//去掉末位
        a = (a * a) % mod;//a的平方
    }
    return re;
}

分析：

基本思想就是将指数二进制，然后分割成a^k1*a^k2...*a^kn，从而降低复杂度。

先定义一个re表示最后的输出答案。然后当指数不为0时，如果末位为1，就要乘上a；如果末位为0，就不乘。然后把用过的末位去掉，方法就是向右移位。最后对a平方。

例如：求12^6%1000(取余还有一种说法就是求末位多少位的整数)

把指数6二进制->110

1.n&1 == 0            2.n&1 == 1               3.n&1 == 1              4. n == 0

   re == 1                  re == 12^2               re == 12^6                break;

   n == 11                 n == 1                       n == 0                       re == 12^6

   a == 12^2             a == 12^4                 a == 12^8                 return;

借鉴博客：https://www.cnblogs.com/luyingfeng/p/3674425.html