1.快速幂取模的思路：

快速幂实现的最基本的理论就是我们离散课上或者数论中学过的一条公式推出的引理。

---

2.引理：

积的取余等于取余的积的取余。

再在这条引理的基础之上，对指数型数据进行拆分以及合并，从而得到我们用的快速幂算法。

---

 

3.快速幂具体分析：

对a^b进行分析。

对于当a和b较小是直接用int或者long存是没有问题的，但是当a和b大到一定程度时，这就不是暴力存就

可以解决的问题了。我们应该怎么去解决这个问题呢？

 

在这里我们需要把注意力放在“大”字上面，正是由于a和b过大才导致的问题。所以我们要想办法不断地减

小a和b的规模，所谓逐个击破。

根据上面的那条引理，我们知道了可以把指数拆开，从这个突破口突破。这里我们就不难想到这样一个算法：

/a是底数，b是指数，mode是取模数，sum是记录取模的结果
int sum = 1;
    a = a % mode; 
    for(int i = 1; i <= b; i++)
    {
        sum = sum * a;
    }
sum = sum % c;

这是直接利用的 引理而写出来的代码，这只是单纯的降低的a的规模，但是这还达不到我们的要求，所以我们

需要进一步改进算法。（当然还可以继续降低啊的规模，即将循环中的那句换成sum = （sum * a）%mode）

 

我们已经实现的降低a的规模，所谓我们要想着怎么降低b的规模。我们首先看两个样例：先看b为偶数的样例

7^16，mode = 3，我们要怎么进行拆分？

 

最基本的拆分是这样的：7*7*7*7*7*7*7*7*7......7，上面的算法只是将其变为1*1*1*1*1*1*1......1，那么怎么减少b

的规模呢？你应该有一点感觉了吧。就是两两合并，将（7^16）变成（49^8），这就降低了b的规模，再利用上面

 

的算法降低a的规模，最终会变成1 *1*1*1*1*1*1*1。是不是感觉整个数简单了很多。

按照这个思路，我们可以多循环几次，从而不断的降低a和b的规模。

 

那么b为奇数怎么办呢？

其实也很简单，我们只要在偶数算法的基础之上，每次把多出来的这个数跳出来，预先取模再带入即可。

从而最终得出快速幂的代码：
 

long long Mode(long long a, long long b, long long mode)
{
    long long sum = 1;
    a = a % mode;
 
    while (b > 0) {
        if (b % 2 == 1)		//判断是否是奇数，是奇数的话将多出来的数事先乘如sum
            sum = (sum * a) % mode;
        b /= 2;
        a = (a * a) % mode;// 不断的两两合并再取模，减小a和b的规模
    }
    return sum;
}

当然有时候你可能会碰到用&的运算符的代码实现，其实和这个大致相同，只不过是用&操作符对b的奇偶性进行判断而已

---

&的操作符：二进制位中，1 & 1 = 1，其余组合均为0

用&实现的代码：

long long Mode(long long a, long long b, long long mode)
{
    long long sum = 1;
    while (b) 
    {
        if (b & 1) 
        {
            sum = (sum * a) % mode;
            b--;
        }
        b /= 2;
        a = a * a % mode;
    }
    return sum;
}

---