一、数学知识

1. 因为 (a * b) % c = [ (a % c) * (b % c) ] % c
   于是(a * a * a * a * ... *a) = [(a % c) * (a % c) * (a % c) ... * (a % c)]
2. 如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则 a * c ≡ b * d (mod m)。这被称为同余关系的乘法性质

核心原理
对于偶数m，a^m^ = (a^2^)^m/2^ 底数平方，指数除2
对于奇数n，a^n^ = a * (a^2^)^n/2^ 底数 * (底数平方，指数除2)（这里的除法为编程中的除法，向下取整）
例：
3^10^
= (3^2^)^5^
= (9)^5^
= 9 * 9 ^4^
= 9 * (9^2^)^2^ //这一步调了很久格式都打不出数字上标，看不懂的话建议在之上写写

因此可以写出快速幂的代码

typedef long long LL;
LL qmi(LL a, LL b)
{
    LL ans = 1; //ans要相乘，因此初始化为0
    while(b)
    {
        if (b % 2 == 1)     //指数为奇数
        {
            ans = ans * a;  //底数 *
            a = a * a;      //底数平方
            b /= 2;         //指数除2
        }
        else
        {
            a = a * a;      //底数平方
            b /= 2;         //指数除2
        }
    }
}

当然，以上代码是计算a^b^的快速方法。如果要快速计算 a^b^ % c，根据数学公式，只需做一点小的改变即可

typedef long long LL;
LL qmi(LL a, LL b, LL c)
{
    LL ans = 1;                     //ans要相乘，因此初始化为0
    while(b)
    {
        if (b % 2 == 1)             //指数为奇数
        {
            ans = (ans * a) % c;    //每个部分依次%c
            a = a * a;
            b /= 2;
        }
        else
        {
            a = (a * a) % c;        //a * a可能溢出，于是%c，这里利用同余关系的乘法性质，%c后结果不变。
            b /= 2;
        }
    }
    return ans;
}

当然，我们可以将在加一点点细节，使代码更简洁，速度更快

typedef long long LL;
LL qmi(LL a, LL b, LL c)
{
    LL ans = 1;
    a %= c;                                 //对底数 a 进行取模操作，以防止在进行乘法运算时出现溢出或超出 c 的范围
    while(b)
    {
        if (b & 1)  ans = (ans * a) % c;    //2进制中，奇数只取决于个位是否为1

        a = (a * a) % c;
        b >>= 1;

    }
    return ans;
}

摘自我的算法基础课笔记
有帮助的话请给我点一个赞！