方法一：拓展欧几里得算法

模板题

需要满足gcd(a,b)能整除n就行

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)//求一个特解
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    ll t, n, m, x, y, sum;
    scanf("%lld", &t);
    while (t--)
    {
        scanf("%lld%lld", &n, &m);
        ll gcd = exgcd(n, m, x, y);
        if (gcd == 1)
        {
            sum = (x % m + m) % m;
            printf("%lld\n", sum);
        }
        else
            printf("-1\n");
    }
    return 0;
}

方法二：快速幂求解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long LL;
int n,m;
LL POW(LL x,LL y,LL p){
    LL re=1;
    while(y){
        if(y&1)re=re*x%p;
        x=x*x%p;
        y>>=1;
    }
    return re;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        int y,p;
        scanf("%d%d",&y,&p);
        if(__gcd(y,p)!=1){
            printf("-1\n");
        }
        else{
            printf("%lld\n",POW(y,p-2,p));
        }
    }
    return 0;
}