求m^n的后三位数（时间复杂度O(logn)）

Problem description:

Given two integers m and n, find the integer represented by the last three digits of $m^n$.

For example, if $m=3$ and $n=9$, the returned number should be $683(3^9=19683)$.

Please give an algorithm with $O(logn)$ complexity.

Note:

In a computer program, when $m$ or $n$ is large, exponential calculations may cause data overflow. Your algorithm should be able to avoid this problem.

Input:

Line 1: two integers $m$ $n$, split by space

Output:

Line 1: one integer

Sample Input 1:

3 9

Sample Output 1:

683

Sample Input 2:

2 10

Sample Output 2:

24

Solution:

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int power(int m,int n) { int lastthree; if (n==0) return 1; else if(n==1) return m%1000; else if(n%2==1){ lastthree = (m%1000)*power(m,(n-1)/2)*power(m,(n-1)/2); return lastthree%1000; } else if(n%2==0){ lastthree = power(m,n/2)*power(m,n/2); return lastthree%1000; } } int main() { int m, n; scanf("%d%d",&m,&n); cout << abs(power(m, n)) << endl; return 0; }

注意：

要求输出$m^n$的后三位，每次只需要计算$m$的后三位即可，因此使用$\%1000$求每次运算的后三位数。采用“分治”（divide and conquer）思想，采用递归，来满足$O(logn)$的时间复杂度。输出注意取绝对值。注意$n=0$的情况。