首页 > 代码库 > 欧几里得(模板)
欧几里得(模板)
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; }
欧几里得(模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。