$对于a^{b} ,可以用O(logb)的时间复杂度求出，使用二进制拆分的思想将b拆分成二进制，分别得出a^{2^{0}},a^{2^{1}}...a^{2^{n}}之后求积即可。$

 1 #include <iostream>
 2 using namespace std;
 3 
 4 long long qmi(int a,int b,int p)
 5 {
 6     long long res = 1,base = a;
 7     while(b)
 8     {
 9         if(b & 1)
10             res = res * base % p;
11         base = base * base % p;
12         b >>= 1;
13     }
14     return res;
15 }
16 
17 int main()
18 {
19     int n;
20     cin >> n;
21     while(n--)
22     {
23         int a,b,p;
24         cin >> a >> b >> p;
25         cout << qmi(a,b,p) << endl;
26     }
27     return 0;
28 }

快速幂求逆元：

乘法逆元的定义：

$若整数b，m互质，并且对于任意的整数a，如果满足b|a，则存在一个整数x，使得a\div b \equiv a\times x(mod m),则称x为b的模m乘法逆元，记为b^{-1}(mod m).b存在乘法逆元的充要条件就是b与模数m互质。当模数m为质数时，b^{m-2}即为b的乘法逆元。$

为了方便，我们直接假设m就是质数，便可以使用快速幂直接求出$b^{m-2}$。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 long long qmi(int a,int b,int p)
 5 {
 6     long long res = 1,base = a;
 7     while(b)
 8     {
 9         if(b & 1)
10             res = res * base % p;
11         base = base * base %p;
12         b >>= 1;
13     }
14     return res;
15 }
16 
17 int main()
18 {
19     int n;
20     cin >> n;
21     while(n--)
22     {
23         int a,p;
24         cin >> a >> p;
25         if(a % p == 0)
26             cout << "impossible" << endl;
27         else
28             cout << qmi(a,p - 2,p) << endl;
29     }
30     return 0;
31 }