快速幂及求逆元

目录

• 快速幂

快速幂

1、快速幂的作用

  快速幂可以帮助我们在\(O(\log k)\)的时间复杂度内计算出\(a^k\quad mod \quad p\)的结果。

2、算法原理

  首先快速幂我们要处理出\(\log k+1\)个数，\(a^{2^0}mod \quad p,a^{2^1}mod\quad p,a^{2^2}mod\quad p,...,a^{2^{\log k}}mod\quad p\)处理完这些数之后就可以计算\(a^k\).我们可以通过二进制的形式去凑。先把k转化成二进制形式，然后在出现1的位置乘上相应的我们前面预处理的数即可。
举个例子吧：
假设要我们算一下\(4^5\quad mod \quad 10\)的结果。
首先我们处理出\(4^{2^0}\quad mod \quad 10=4\), \(4^{2^1}\quad mod \quad 10=6\), \(4^{2^2}\quad mod \quad 10=6\).然后5的二进制表示是101，我们在是1的位置上乘上相应的数，及\(4^{2^0+2^2}\),展开就是\(4^{2^0}+4^{2^2}\)查表得\((4*6)\quad mod\quad 10=4\).然后就可以啦~
例题
快速幂例题

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

long long qmi(int a, int k, int p)
{
     long long res = 1;
     while (k)
     {
          if (k & 1) //如果这一位是1的话我们就乘上相应的数
               res = (long long)res * a % p;
          k >>= 1;      //去掉最后一位
          a = (long long)a * a % p;     //每次算出相应的a值，及上一个值的二次方
     }
     return res;
}

void solve()
{
     int a, k, p;
     cin >> a >> k >> p;
     cout << qmi(a, k, p) << endl;
}

int main()
{
     int T;
     cin >> T;
     while (T--)
     {
          solve();
     }
     return 0;
}

3、逆元

我们要求$${a\over b}\equiv a\times x \quad (mod \quad p)$$我们两边同时乘上一个b得$$a \equiv a\times x \times b\quad(mod\quad p)$$我们约去a得到：$$b\times x\equiv 1\quad(mod\quad p)$$，然后b和p互质我们可以想到费马小定理那么x就等于\(b^{p-2}\)，这样的话就转化成了一个快速幂问题。如果大家不清楚费马小定理的话可以看这篇文章。欧拉定理及费马小定理
例题
逆元例题

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

long long pmi(int a, int p)
{
     long long res = 1;
     int k = p - 2;
     while (k)
     {
          if (k & 1)
               res = (long long)a * res % p;
          k >>= 1;
          a = (long long)a * a % p;
     }
     return res % p;
}

void solve()
{
     int n, p;
     cin >> n >> p;
     if (n % p)
          cout << pmi(n, p) << endl;
     else
          cout << "impossible" << endl;
}

int main()
{
     ios::sync_with_stdio(false);
     int T;
     cin >> T;
     while (T--)
     {
          solve();
     }
     return 0;
}