exgcd

#include<cstdio>
using namespace std;

int a,b,x,y,k;

inline void exgcd(int a,int b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}

int main(){
    scanf("%d%d",&a,&b);
    exgcd(a,b);
    printf("%d\n",(x%b+b)%b);
}

exgcd

原文：https://www.cnblogs.com/Y15BeTa/p/10960102.html