C++14(g++5.4) 解法, 执行用时: 524ms, 内存消耗: 4316K, 提交时间: 2020-06-22 23:24:19

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fpow(ll a,ll b,ll mod){
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		b/=2;a=(a*a)%mod;
	}
	return ans%mod;
}

int main()
{
	int t;
	cin>>t;
	while(t--){
		ll y,p;
		cin>>y>>p;
		if(__gcd(y,p)!=1) cout<<-1<<endl;
		else cout<<fpow(y,p-2,p)%p<<endl;
	}
	return 0;	
} 

C++(clang++ 11.0.1) 解法, 执行用时: 129ms, 内存消耗: 1828K, 提交时间: 2023-02-03 19:18:57

# include <bits/stdc++.h>
using namespace std;
int inv(long long a,long long b){
	return a==1?1:(b-b/a)*inv(b%a,b)%b;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		long long a,b;
		scanf("%lld%lld",&a,&b);
		if(a%b==0){
			printf("-1\n");
			continue;
		} 
		a=a%b;
		printf("%d\n",inv(a,b));
	}
}