void exgcd(ll a,ll b,ll &x,ll &y) { if(b==0){x=1;y=0;return;} exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y; }
扩展欧几里得算法
原文：http://www.cnblogs.com/lalalatianlalu/p/8016690.html
