题目链接

a, b 互质才有乘法逆元的原因

假设x是a对于b的乘法逆元，则有 ax = 1 mod b, 即x是方程 ax + by = 1的一个整数解。
但是形如 ax + b*y 的最小正整数为gcd(a,b)。
此结论可以通过扩展欧几里得算法（EEA）的正确性得到。
而1又是最小的非零自然数，所以只有当gcd(a,b)=1时，a才有对于b的乘法逆元。

费马小定理是欧拉定理的特例

由欧拉定理知道，如果a, p 互质，则 a^φ(p) ≡ 1 (mod p)
那么 当p是质数时1，φ(p) = p - 1, 所以 a^(p-1) ≡ 1 (mod p) ,所以 a * a^(p-2) ≡ 1 (mod p) ， 所以a^(p-2)是a的乘法逆元,这便是费马小定理

#include <iostream>
using namespace std;

typedef long long ll;
int n, a, p;

int qmi(int a, int m, int p){
    int res = 1;
    while (m){
        if (m & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        m >>= 1;
    }

    return res;
}

int main(){
    cin >> n;
    while (n --){
        scanf("%d%d", &a, &p);
        if (a % p) printf("%d\n", qmi(a, p - 2, p));
        // 这里只有当a和p互质的时候才有逆元，而p又是质数，所以a一定不能有因数p, 所以只需判断(a%p != 0) 即可
        else puts("impossible");
    }

    return 0;
}