快速幂

• 可以在 O(logb) 的事件复杂度之内求出 a ^ b mod p 的结果。本质就是把 b 分成了 2 ^ 0 + 2 ^ 1 + 2 ^ 2 ... + 2 ^ n ，分别求出来然后乘在一起。

快速幂求逆元

• 如果 a / b 是一个整数的话，我们希望不做除法，因为做除法取余数是一个很麻烦的过程。需要注意的是这里的 $b^{-1}$ 只是一个符号。并不是指b的-1次方。

• 比如 3 的一个模5 逆元就是 2 。 2 * 3 = 6, 6 % 5 = 1 。

• 其实这道题的意思 就是给你 a 和 p ，让你求 b ，其中 a * b % p = 1 。

• 

• 根据费马小定理，这里要求出 a 的模 p 逆元，可以求 $a^{p-2}$ 。也就是说套上一题的快速幂模板，求出 $a^{p-2}$ 即为 a 的模 p 逆元。

• 代码如下

  #include <iostream>

  using namespace std;

  typedef long long ll;

  ll ksm(ll a, ll b, ll p)
  {
      if (b == 0) return 1;
      ll res = 1;
      while (b)
      {
          if (b & 1)
          {
              res = res * a % p;
          }
          b >>= 1;
          a = a * a % p;
      }

      return res;
  }

  int main()
  {
      int T;
      cin >> T;
      while (T -- )
      {
          ll a, p;
          cin >> a >> p;
          ll res = ksm(a, p - 2, p);
          if (a % p == 0) puts("impossible");
          else printf("%d\n", res);
      }

      return 0;
  }