Question

杭电OJ看到一个答案，不明白思路求告知

题目：
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 312 66789 100000 0

Sample Output
8984
代码：

怎么理解他的思路？

Answer 1

简单来说 就是对于任意的m*n 最后三位为

m*n%1000 它的值和((m%1000) * (n%1000))%1000的值是相同的

这个是一个简单的数学题 相信你可以理解

这样就有一个朴素的思路

long func(long a, long b)
{ 
    long r = 1;
    a %= 1000;
    while(b--)
    {
        r*=a;
        r%=1000;
    }
}

不过这样做需要执行b次乘法和模除 用专业一点的话说 它的时间开销是O(n)的

那么如果每次采用分组的方式

即对于a*a*a*a...*a(b个a) 不是依次来处理 而是一次处理一半

那么就是你看到的程序了

即a^b = a^(b/2) * a^(b/2) (当b为偶数)

a^b = a^(b/2) * a^(b/2) *a(当b为奇数)

同样应用最开始的(m*n)%1000 = ((m%1000) * (n%1000))%1000 的规律

就变成了你说的程序