扩展欧几里得
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } else { ll res=exgcd(b,a%b,y,x); y-=x*(a/b); return res; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } else { ll res=exgcd(b,a%b,y,x); y-=x*(a/b); return res; } } |