C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 472K, 提交时间: 2022-08-18 22:56:11

#include<iostream>
using namespace std;
int a,b;
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return ;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int main(){
	cin>>a>>b;
	int x,y;
	exgcd(a,b,x,y);
	printf("%d",(x+b)%b);
}

C++(clang++11) 解法, 执行用时: 7ms, 内存消耗: 508K, 提交时间: 2020-12-02 21:26:51

#include<bits/stdc++.h>
using namespace std; 
int a,b,x,y; 
void gcd(int a,int b)
{
	if (b==0) { x=1; y=0; return;}
	gcd(b,a%b); 
	int z=x; x=y; y=z-y*(a/b); 
}
int main()
{
	cin>>a>>b; 
	gcd(a,b); 
	cout<<(x%b+b)%b; 
}

Python3 解法, 执行用时: 41ms, 内存消耗: 4596K, 提交时间: 2023-07-31 15:03:30

a,b=map(int,input().split())
print(pow(a,-1,b))