1.辗转相除法,用来求两个数的最大公约数
//普通的gcd int gcd(int a, int b) { if (b == 0)return a; return gcd(b, a % b); } //快速的gcd(我觉得好像也没多快) int qGCD(int a, int b) { if(a == 0) return b; if(b == 0) return a; if(!(a & 1) && !(b & 1)) // a % 2 == 0 && b % 2 == 0; return qGCD(a >> 1, b >> 1) << 1; else if(!(b & 1)) return qGCD(a, b >> 1); else if(!(a & 1)) return qGCD(a >> 1, b); else return qGCD(abs(a - b), min(a, b)); }
2.拓展欧里几德算法,用来求解ax+by=1的方程
int extgcd(int a, int b, int& x, int& y) { int d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1;y = 0; } return d; }