Mathematical knowledge: fast power inverse element - fast power

subject ：AcWing 876. Fast power inverse
Given n Group a_i,p_i, among p_i Prime number , seek a_i model p_i Multiplicative inverse element of , If the inverse element does not exist, output impossible.

Be careful ： Please return to 0∼p−1 The inverse element between .

Definition of multiplicative inverse

If integer b,m Coprime , And for any integer a, If meet b|a, Then there is an integer x, bring a/b≡a*x(mod m), said x by b The mold m Multiplicative inverse element , Write it down as b⁻¹(modm).
b The necessary and sufficient condition for the existence of multiplicative inverse is b And modulus m Coprime . When modulus m Prime number ,b^m−2 That is to say b Multiplicative inverse element of .

Input format
The first line contains integers n.

Next n That's ok , Each row contains an array a_i,p_i, Data assurance p_i Prime number .

Output format
The output, n That's ok , Each group of data outputs a result , Each result takes up one line .

if a_i model p_i The multiplicative inverse of exists , Then an integer is output , Represents the inverse element , Otherwise output impossible.

Data range
1≤n≤10⁵,
1≤a_i,p_i≤2∗10⁹

sample input ：

3
4 3
8 5
6 3

sample output ：

1
2
impossible

Topic analysis ：
When n Prime number , You can use the fast power to find the inverse element ：
a / b ≡ a * x (mod n)
Ride on both sides b Available a ≡ a * b * x (mod n)
namely 1 ≡ b * x (mod n)
Same as b * x ≡ 1 (mod n)
From Fermat's theorem , When n Prime number
b ^ (n - 1) ≡ 1 (mod n)
Remove one b Come out and get b * b ^ (n - 2) ≡ 1 (mod n)
Therefore, when n Prime number ,b Multiplicative inverse element of x = b ^ (n - 2)

#include <iostream>

using namespace std;

const int N = 100010;
typedef long long LL;

LL qmi(int a,int k,int p)
{
    
    LL res=1%p;
    while(k)
    {
    
        if(k&1)res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}
int main()
{
    
    int n;
    scanf("%d",&n);
    
    while(n--)
    {
    
        int a,p;
        scanf("%d%d",&a,&p);
        int res=qmi(a,p-2,p);
        if(a%p)cout<<res<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}