C++ 解法, 执行用时: 763ms, 内存消耗: 1196K, 提交时间: 2021-10-26 21:10:47

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll exGCD(ll a,ll b,ll& x,ll& y){
	if(!b)return x=1,y=0,a;
	ll d=exGCD(b,a%b,y,x);
	y-=x*(a/b);
	return d;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		ll a,b,x,y;
		cin>>a>>b;
		ll d=exGCD(a,b,x,y);
		if(d!=1)cout<<-1<<endl;
		else cout<<(x+b)%b<<endl;
	}
}

Python3 解法, 执行用时: 1923ms, 内存消耗: 5428K, 提交时间: 2022-04-21 09:37:28

def exGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exGCD(b, a%b)
    return g, y1, x1-a//b*y1

t = int(input())

for i in range(t):
    a, b = map(int, input().split())
    g, x, y = exGCD(a, b)
    if g != 1:
        print(-1)
    else:
        print(x % b)

pypy3 解法, 执行用时: 815ms, 内存消耗: 34688K, 提交时间: 2022-08-02 11:07:37

def exGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exGCD(b, a % b)
    return g, y1, x1 - a // b * y1
for i in range(int(input())):
    a, b = map(int, input().split())
    g, x, y = exGCD(a, b)
    print('-1' if g != 1 else x % b)