【模板】各种欧几里得

1 //a > b 2 int gcd(int a , int b) 3 { 4     return b ? gcd( b , a % b ) : a ; 5 } 6  7 int lcm(int a , int b) 8 { 9     return a / gcd( a , b ) * b;10 }

 

 

1 int gcd(int n,int m)//n>m 2 { 3     //最大公约数 4     int r; 5     while(m) 6     { 7         r = n%m; 8         n = m; 9         m = r;10     }11     return n;12 }13 14 int kgcd(int a,int b)15 {16     if(!a) return b;17     if(!b) return a;18     if(!(a&1) && !(b&1))19         return kgcd(a>>1,b>>1)<<1;20     else if(!(b&1)) return kgcd(a,b>>1);21     else if(!(a&1)) return kgcd(a>>1,b);22     else return kgcd(abs(a-b),min(a,b));23 }24 25 //扩展欧几里得26 //求方程ax+by+c = 0有多少整数解27 int extgcd(int a,int b,int &x,int &y)28 {29     if(!b)30     {31         x=1;32         y=0;33         return a;34     }35     int d = extgcd(b,a%b,x,y);36     int t = x;37     x=y;38     y=t-a/b*y;39     return d;40 }