用分治法求a的n次幂

分治法求解一个数a的n次幂，也称为快速幂算法（Exponentiation by Squaring），它是一种高效的计算幂的数学技巧。其基本思想是利用指数运算的性质，将大指数分解成若干个较小的指数相乘。分治法在这里的应用可以分为以下步骤：

1. **基本情况**：如果n为0，则结果为1（因为任何数的0次幂都等于1）。如果n为正整数1，则结果就是a本身。

2. **递归情况**：对于较大的n（>1），我们可以将其拆分成两个相等的部分（除以2取整，得到n1和n2），然后计算a^(n1) 和 a^(n2)，然后将它们相乘。这是因为a^n = a^(n1 * 2) = (a^(n1))^2，这就是分治的核心——将问题规模减半。

3. **递归应用**：对每个子问题分别运用相同的分治策略，直到n1和n2足够小可以直接通过循环计算，然后返回结果。这通常涉及到一个while或for循环，用指数n1从1递减到0，每次更新a值为a * a。

4. **结束递归并返回结果**：当n1为0时，停止递归，此时的结果就是原问题的最终答案。如果是循环计算阶段，直接返回a^(n1)。

下面是这个过程的伪代码示例：

function power(a, n):
    if n == 0:
        return 1
    elif n % 2 == 0:   // 如果n是偶数
        half = power(a, n / 2)
        return half * half
    else:              // 如果n是奇数
        half = power(a, (n - 1) / 2)
        return a * half * half