[4.4 detailed explanation of fast power and inverse element of fast power]

$moregoodOfreadingreadbodyExamination$

4.4.1 Fast power explanation

Concept

• Quickly find $a^k\mathrm{m}\mathrm{o}\mathrm{d}p$ Result

thought

• Preprocessing $a^{2^0},a^{2^1},a^{2^2}\dots a^{2^{lo{g}_2^k}}$ Result
• Is that $k=2^{p_1}+2^{p_2}+\cdots +2^{p_i}$
• namely ：$a^k=a^{2^{p_1}}\times a^{2^{p_2}}\times \cdots \times a^{2^{p_i}}$
• about $a^{2^0}\times a^{2^0}=a^{2^1},a^{2^1}\times a^{2^1}=a^{2^2}$, namely $a^{2^{p_i}}=a^{2^{p_{i-1}}}\times a^{2^{p_{i-1}}}$
• in summary , Record during operation $a^{p_i}$ Value , And the result of multiplication
• take $k$ Into binary representation , Bitwise >> operation , If the current bit is $1$, Then the result of the current multiplication $\times a^{p_i}\mathrm{m}\mathrm{o}\mathrm{d}p$
• Every time the $k$ Conduct >> After the operation , to update $a^{p_{i+1}}=a^{p_i}\times a^{p_i}\mathrm{m}\mathrm{o}\mathrm{d}p$
• When binary $k$ No more >> when , The result of multiplication is the answer

Templates

typedef long long LL;

LL qmi(LL a,LL k,LL p){
      // Calculation  a^k % p  Result 
    
    LL res=1;  // Record the cumulative result 
    
    while(k){
    
        
        if(k&1) res=res*a%p;  //k&1 Get the current bit , if 1 Then I'm tired a^pi
        a=a*a%p;  // to update a^pi
        k>>=1;  // Move right 1 position 
    }
    
    return res;
    
}

---

4.4.2 Fast power inverse

---

Concept

• congruence ： set up $m$ As a positive integer ,$a$ and $b$ Is an integer , if $m|a-b$, said $a$ model $m$ Congruence with $b$, or $a$ And $b$ model $m$ congruence , Write it down as $a\equiv b(modm)$
• if $ab\equiv 1(modm)$, said $b$ by $a$ The mold $m$ The inverse , Write it down as $a^{-1}(modm)$ or $a^{-1}$

Be careful

• $a$ The mold $m$ Inverse existence $\iff$$a$ And $m$ Coprime

• When $m$ Prime number , Use Fermat's theorem to find

• When $m$ When not prime , Use the extended Euclidean algorithm to find

thought

• Use fast power to realize $m$ When it is a prime number, use Fermat's theorem to find the inverse element

• Fermat's small Theorem ： set up $p$ As a prime number , And $a$ And $p$ Coprime , be $a^{p^{-1}}\equiv 1(modp)$

• $$\begin{array}{rl}{a}^{p^{-1}}\equiv 1(modp)\to & a\times a^{p^{-2}}\equiv 1(modp)\\ & a\times b\equiv 1(modp)\\ & namely：b=a^{p^{-2}}\end{array}$$

---

Template example 876. Fast power inverse

Original link

describe

Given n Group ai,pi, among pi Prime number , seek ai model pi 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(modm), said x by b The mold m Multiplicative inverse element , Write it down as b−1(modm).
b The necessary and sufficient condition for the existence of multiplicative inverse is b And modulus m Coprime . When modulus m Prime number ,bm−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 ai,pi, Data assurance pi Prime number .

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

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

Data range
1≤n≤105,
1≤ai,pi≤2∗109
sample input ：

3
4 3
8 5
6 3

sample output ：

1
2
impossible

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL qmi(LL a,LL k,LL p){
    
    
    LL res=1;
    
    while(k){
    
        
        if(k&1) res=res*a%p;
        a=a*a%p;
        k>>=1;
        
    }
    
    return res;
    
}

int main(){
    
    
    int n;
    
    cin>>n;
    
    while(n--){
    
        
        int a,p;
        
        cin>>a>>p;
        
        if(a%p==0) cout<<"impossible"<<endl;  //a And p Non coprime means that there is no inverse element 
        else cout<<qmi(a,p-2,p)<<endl;
        
    }
    
    return 0;
        
}

---