扩展欧几里德算法

cmwqf · 2018-04-30 17:33:21 · 个人记录

#include<cstdio>
using namespace std;
int d,x,y,a,b;
void gcd(int a,int b,int &d,int &x,int &y)
{
    if(!b) { d=a;x=1;y=0; }
    else { gcd(b,a%b,d,y,x); y-=x*(a/b); }
}
int main()
{
    scanf("%d%d",&a,&b);
    gcd(a,b,d,x,y);
    printf("%d %d",x,y);
    return 0;
}