【模板】gcd和exgcd

1 int gcd(int a,int b)
2 {
3     return !b?a:gcd(b,a%b);
4 }

 1 int exgcd(int a,int b,int& x,int& y)
 2 {
 3     int d=a;
 4     if(b){
 5         d=exgcd(b,a%b,y,x);
 6         y-=(a/b)*x;
 7     }
 8     else{
 9         x=1;y=0;
10     }
11     return d;
12 }