快速幂求逆元

给定 $ n $ 组 $ a_i, p_i $，其中 $ p_i $ 是质数，求 $ a_i $ 模 $ p_i $ 的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 $ 0 sim p-1 $ 之间的逆元。

乘法逆元的定义

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

想法

题目中说了$ p_i $ 是质数
可以通过快速幂算出来逆元

思路

$ b $ 存在乘法逆元的充要条件是 $ b $ 与模数 $ m $ 互质。当模数 $ m $ 为质数时，$ b^{m-2} $ 即为 $ b $ 的乘法逆元。

证明：

[a / b equiv a times x pmod m ]

[a / b equiv a times b^{-1} pmod m ]

[frac{1}{b} equiv b^{-1} pmod m ]

[1 equiv b^{-1} times b pmod m ]

[b^{-1} times b equiv 1pmod m ]

根据费马小定理

(如果p是一个质数，而整数a不是p的倍数，则有a^{p-1}≡1pmod p)

故$$b^{m-1}≡1pmod m$$

[b times b^{m-2} equiv 1pmod m ]

[b times b^{m-2} equiv b^{-1} times b equiv 1pmod m ]

[b times b^{m-2}= b^{-1} times b ]

[b^{-1}=b^{m-2} ]

[x = b^{m-2} ]

所以

1. 当(b)与(m)互质的时候，逆元为(b^{m-2})

2. 当(b)与(m)不互质（即(b)为(m)的倍数）的时候，逆元不存在

(b times x % m = 0)

(x)无论多少(b)都有因数(m)，因此逆元不存在

码来！

#include <iostream>
using namespace std;
typedef long long LL;

LL quickPow(int a, int b, int p)
{
    LL res = 1 % p;
    
    while(b)
    {
        if(b & 1) res = res * a % p;
        
        b >>= 1;
        
        a = a * (LL)a % p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        
        if(a % p == 0) puts("impossible");
        else printf("%dn", quickPow(a, p - 2, p));
        
    }
    return 0;
}

注意：快速幂算法只有当(p)是质数是才可以使用