# 快速幂

***

快速幂用于快速计算指数（$$2^n$$），主要思想是二分。

由于计算机计算单个乘法比多个乘法快得多，所以利用二分的思想来减少乘法运算次数可以提高速度。

例：$$7^{10} = 7*7*7\*...*7$$ 需要计算9次乘法，而先计算$$7^5$$再计算$$7^{10}$$，就只用计算$$7^5 = 7*7*7*7*7$$和$$7^{10}=7^5*7^5$$，只用5次乘法。

以此类推，得到一个递归二分的策略：

$$
n是奇数：a^n = a^{n-1}\*a^n\ n是偶数：a^n = a^{n/2}\*a^{n/2}\ n=0：a^n = 1
$$

写成代码：

```
typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        ll temp = qpow(a, n / 2);
        return temp * temp;
    }
}
```

这是递归版本的快速幂。 可以看到，这里二分的操作可以和二进制的右移对应，于是可以用二进制的方式理解：

$$7^{10} =7^{\[1010]\_2}$$ ，于是$$7^{10}=7^{\[1000]\_2} \* 7^{\[0010]\_2}$$

由于上面的递归形式递归会耗费时间，所以用二进制的思路将上面的递归改成循环形式会更好。

具体方法：由于每个二进制位表示一次平方，所以我们对n的每个二进制位，让底数进行一次自乘，如果对应的二进制位为1，则将此时的底数乘给ans，达到例如 $$7^{\[1010]\_2}=7^{\[1000]\_2} \* 7^{\[0010]\_2}$$的效果。

代码：

```
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/kuai-su-mi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.