扩展欧几里得

#include<cstdio>

using namespace std;
typedef long long ll;

ll A,m;

void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lld%lld",&A,&m);
        if(A%m==0)  puts("impossible");
        else
        {
            ll x,y;
            exgcd(A,m,x,y);
            x=(x%m+m)%m;
            printf("%lld\n",x);
        }
    }
    return 0;
}

快速幂 公式法

#include<cstdio>

using namespace std;
typedef long long ll;

ll A,m;

ll qpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret=ret*a%m;
        b>>=1;
        a=a*a%m;
    }
    return ret;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lld%lld",&A,&m);
        if(A%m==0)  puts("impossible");
        else
            printf("%lld\n",qpow(A,m-2));
    }
    return 0;
}