欧几里德算法求最大公约数

typedef long long ll;//gcd(a,b)返回a,b的最大公约数ll gcd(ll a, ll b) {    return 0 == b ? a : gcd(b, a%b);}

扩展欧几里德算法

typedef long long ll;//求整数x和y，使得ax+by=d，且|x|+|y|最小，其中d=gcd(a,b)//即使a,b在int范围内，x,y也有可能超出int范围void gcd(ll a, ll b, ll &d, ll& x, ll& y) {    if (!b) { d = a; x = 1; y = 0; }    else { gcd(b, a%b, d, y, x); y -= x*(a / b); }}