//gcd LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); } //exgcd LL exgcd(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);} }
模板——扩展欧几里得算法
原文：http://www.cnblogs.com/Kiraa/p/5767211.html
