快速幂

快速幂也叫欧拉降幂、反复平方法。是数论中常客的常客了。 使用背景：一般看到幂运算的时候就可以考虑把快速幂拿出来了。

快速幂的时间复杂度是O(logn)，举个栗子，假如要处理109的数据，大概只需要运算30次，比O(n2)的效率高了很多个档次了。

快速幂算法的原理说简单一点，就是把幂二进制化，比如对于x²²

22的二进制是(10110)₂

那么对于x²²按照快速幂的原理的拆分法，拆出来就是下面的效果:

x²² = x¹⁶ * x⁴ * x²

基本了解的算法怎么实现的，那么下面咱们具体从例题中落实吧

算法模板

幂运算实现流程：

幂运算代码实现：

快速幂
求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

例题描述

参考代码

疑难点剖析

小心int溢出

因为快速幂中是指数函数彼此之间的乘积运算。当数据十分庞大的时候，int可能装不下，所以要强转为long long类型

    if(k&1) res = (LL)res*a%p;
    k>>=1;
    a=(LL)a*a%p;

拓展欧几里得算法

前提引入

拓展欧几里得算法是在欧几里得算法的基础上，证明裴蜀定理而产生的的。

裴蜀定理：

对于任意整数a,b，存在一对整数x,y，满足 ax + by = gcb(a,b)

下图是李煜东老师书中对定理证明的详细步骤。后续算法的代码落实也是依赖于这个证明中进行公式变换的部分

算法模板

算法实现流程

算法代码描述：

扩展欧几里得算法
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;

例题描述

参考代码(C++版本)

疑难点剖析

注意要拓展欧几里得算法实现的时候，在函数参数中，要传入系数x和y的引用