题目描述

快速幂求逆元

逆元：将除法变成乘法
a/b 同余于 a*x(mod p)

整数x即为b的逆元

由费马定理得：b^(p-1) 同余于1（mod p）
可以转化成：b * b^(p-2)

所以转化成用快速幂求b^(p-2) mod p;

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1)res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,k,p;
        cin>>a>>p;
        int res=qmi(a,p-2,p);
        if(a%p)cout<<res<<endl;     //若if(res)，则没有考虑p-2=0的情况
        else cout<<"impossible"<<endl;
    }
    return 0;
}