快速幂求逆元

原题链接：876. 快速幂求逆元 - AcWing题库

解题思路

题目中提到了

而题目中的给的p是质数我们就可以利用快速幂求b(a)的乘法逆元b(a) ^ m-2

还有一点我们再判断b(a)是不是和p互质就可以了

源代码

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n;
    cin >> n;

    for(int v = 0;v < n;v ++)
    {
        long long a,p;
        scanf("%lld%lld",&a,&p);
        if(a % p == 0)
        {
            printf("impossible\n");
            continue;
        }
        long long re = 1;
        int t = p - 2;
        while(t)
        {
            if(t & 1)re = re * a % p;
            a = a * a % p;
            t >>= 1;
        }
        printf("%lld\n",re);
    }

    return 0;
}