模板专栏|欧几里得(模板)

int gcd(int n,int m)//n>m { //最大公约数 int r; while(m) { r = n%m; n = m; m = r; } return n; }int kgcd(int a,int b) { if(!a) return b; if(!b) return a; if(!(a&1) && !(b&1)) return kgcd(a>>1,b>>1)<<1; else if(!(b&1)) return kgcd(a,b>>1); else if(!(a&1)) return kgcd(a>>1,b); else return kgcd(abs(a-b),min(a,b)); }//扩展欧几里得 //求方程ax+by+c = 0有多少整数解 int extgcd(int a,int b,int &x,int &y) { if(!b) { x=1; y=0; return a; } int d = extgcd(b,a%b,x,y); int t = x; x=y; y=t-a/b*y; return d; }


    推荐阅读