数论 --- 快速幂、快速幂求逆元

快速幂

可以在时间复杂度为 O(log^k) 内，快速地求出来 a^k mod p 的结果，其中 a、p、k 都可以在 10^9 范围内

LeetCode+ 46 - 50_小雪菜本菜的博客-CSDN博客

如果用暴力做法需要循环一遍，循环 k 次，k 等于 10^9，时间复杂度为 O(10^9)

如果 k = 10^9，快速幂可以在 O(log10^9) 之内把它计算出来，也就是大概只需要 30 次运算

快速幂的核心思路是反复平方法，需要预处理出来下面这些值，范围 [ 0，logk ]

预处理的时间复杂度是 logk，一共有 logk 个数

把这些值预处理完之后，怎么把 a^k 组合出来呢？

把 a^k 拆成若干个前面预处理出来的数的乘积的形式就可以了，也就是把 k 拆成前面若干个数的和，也就是把 k 化成二进制就可以了

k 的二进制表示、可拆分的结果如下，k 的二进制表示里面所有是 1 的位把对应的次幂加上就可以了

在计算的时候，最多拆成 logk 个数相乘，整个算法的时间复杂度为 O(logk)

怎么把这 logk 个数预处理出来呢？

每一个数都是上面这个数的平方 mod p，只需要从前往后平方 k 次，就可以把这 logk 个数预处理出来了。预处理完之后，直接把 a^k 分成前面若干个数的乘积就可以了，其实就是把 k 拆成 2 的若干个次幂相加，也就是看 k 的二进制表示里面哪些位是 1，就把 1 对应的这些位乘起来就可以了

下面举一个例子，求 4^5 mod 10 的结果，注意 p 不一定是质数，先预处理，再把 4^5 拆分

读入数据比较多，建议用 scanf 来读入

#include <iostream>
#include <algorithm>

using namesapce std;
//由于模10^9 并且有乘积 两个10^9相乘所以可能会爆int需要写成LL
typedef long long LL;

//返回 a^k % p 的结果
int qmi(int a,int k,int p)
{
    //定义答案
    int res = 1;
    //求 k 的二进制表示
    //当 k!=0
    while(k)
    {
        /* 
            k & 1 就是看 k 的个位是多少,如果当前 k 的末位是 1,就乘上 a^2^0
            注意 a 是不断变化的,是不断反复平方的,一开始的时候 a 是第一项也就是 a^2^0,也就是 a 自己
        */
        if(k & 1) res = (LL)res * a % p;
        /* 
            每次迭代的时候把 k 的末位删掉,因为末位已经计算过了
            看k的二进制表示的下一位,下一位对应的 a 也应该把 a 变成下一个
        */
        k >>= 1;
        //把 a^2^0 变成下一个也就是 a^2^1,也就是把 a 平方
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    //一共 n 组数据
    scanf("%d", &n);
    //每组 a,k,p
    while(n -- )
    {
        int a, k, p;
        scanf("%d%d%d", &a,&k, &p);
        //直接返回 a^k % p
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

快速幂求逆元

什么是逆元呢？下面给出乘法逆元的定义，如果 b 和 m 互质，并且 b 能整除 a 的话，那么就存在一个整数 x 使得 a / b 同余 于 a * x mod m，就称 x 是 b 模 m 的乘法逆元，记作 b^-1(mod m)

如果 a / b 是一个整数的话，我们希望不做除法，因为取余数除法是一件很麻烦的事情，我们希望把除法变成乘法，希望找到一个数使得 a / b 的余数是同余 a * x(mod m)，如果对于某一个 b 能找到一个 x，使得 a / b 和 a * x(mod m) 余数相同的话，就把 x 叫作 b 模 m 的逆元，记作 b^-1(mod m)

b 的逆元是一个标记，不是 b^-1，是一个整数，我们可以把所有除 b 的情况转换成乘上 b 的逆元的情况

把除法变成乘法比较好，因为数论里面除法不一定是一个整数，两个整数相乘还是整数，两个整数相除不一定是整数

逆元的性质

质数的定义

针对所有大于 1 的自然数( 从 2 开始的整数 )来定义的：2、3、4 . . . 所有小于等于 1 的整数，既不是质数也不是合数

在大于 1 的整数中，如果只包含 1 和它本身这两个约数，就被称为质数，或者叫素数

题目需要求逆元，给我们一个 b，要求找到一个 x，使得 b * x ≡ 1 (mod p)，给定的 p 一定是质数，由于 p 是质数，由费马小定理，如果 b 和 p 互质，会有 b^p-1 ≡ 1(mod p)，拆分一个 b，b * b^p-2 ≡ 1(mod p)，如果 p 是质数，根据逆元的性质，b 的逆元就是 b^p-2，也就是说 b^p-2 就是 b % p 的逆元，由于 p 是质数，所以 p 大于等于 2，所以 p - 2 大于等于 0，一定是合法的，所以这道题目让我们求的是 a^p-2 % p 的结果

存在无解的情况，如果 b 是 p 的倍数的时候就是无解的，如果 b 和 p 不互质一定无解的，由于 b 是 p 的倍数，那么 b * x 也一定是 p 的倍数，mod p 一定余 0，不可能余 1，只有在这种情况下是无解的

如果 b 不是 p 的倍数，由于 p 是质数，所以 b 和 p 一定互质，由费马定理，b^p - 1 一定 % p  余 1，所以一定存在逆元，由费马定理能构造出一组解

当 p 是质数的时候可以这样求，如果 p 不是质数就不能用费马定理，费马定理要求 p 一定是质数

#include <iostream>
#include <algorithm>

using namesapce std;
//由于模10^9 并且有乘积 两个10^9相乘所以可能会爆int需要写成LL
typedef long long LL;

//返回 a^k % p 的结果
int qmi(int a,int k,int p)
{
    //定义答案
    int res = 1;
    //求 k 的二进制表示
    //当 k!=0
    while(k)
    {
        //当前k的末位是1
        if(k & 1) res = (LL)res * a % p;
        //把k的末位删掉
        k >>= 1;
        //把a平方
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n -- )
    {
        //输入一个a和p 求a^p-2%p
        int a, p;
        //用res表示答案 把答案先求出来
        int res = qmi(a, p - 2, p);
        scanf("%d%d", &a, &p);
        //如果 a % p != 0,说明 a 不是 p 的倍数,直接把 res 输出就可以了 特判 2 是质数 4 % 2 不互质不输出
        if(a % p) printf("%d\n", res);
        //否则说明一定无解 a 一定是 p 的倍数
        else puts("impossible");
    }
    return 0;
}