C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2018-09-09 15:33:33

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

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 468K, 提交时间: 2019-11-04 18:37:29

#include<cstdio>
void exgcd(int a,int b,int &x,int &y) {!b?(x=1,y=0):(exgcd(b,a%b,y,x),y-=a/b*x);}
int main()
{
    int a,b,x,y;
    scanf("%d%d",&a,&b);
    exgcd(a,b,x,y);
    printf("%d",(x%b+b)%b);
}

pypy3 解法, 执行用时: 125ms, 内存消耗: 25836K, 提交时间: 2022-04-21 09:39:21

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

a, b = map(int, input().split())
g, x, y = exGCD(a, b)
print(x % b)

Python3 解法, 执行用时: 40ms, 内存消耗: 4592K, 提交时间: 2023-07-31 15:19:10

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