数论-最大公约数和最小公倍数

简谈最大公约数和最小公倍数

a,b的最大公约数用gcd(a, b)表示

a,b的最小公倍数用lcm(a, b)表示

最大公约数

辗转相除法(Euclid algorithm)求最大公约数

原理是：gcd(a, b) = gcd(a, b-a)

证明：

设 z|a, z|b, 则z|(b-a)

设 z不是a的因子，则z不伤a， b-a的公因子

设 z|a，z不是b的因子，则z不是a，b-a的公因子

递归求，边界是：b == 0 时 gcd(a, b) = a;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

二进制算法

if x == y ,GCD(x, y) = x;

else :

if x,y都为偶数，GCD(x, y) = 2 * GCD(x/2, y/2);

if x为偶数，y为奇数，GCD(x, y) = GCD(x/2, y);

if x为奇数，y为偶数，GCD(x, y) = GCD(x, y/2);

if x,y都为奇数，GCD(x, y) = GCD(x-y, y);

#include <iostream> using namespace std; inline int Bianary_gcd(int x, int y) { if(x == 0) return y; if(y == 0) return x; int i, j; //记录剔除2的次数 for(i = 0; (x&1) == 0; i ++) x >>= 1; //x剔除2 for(j = 0; (y&1) == 0; j ++) y >>= 1; //y剔除2 while(true) { if(x < y) x^=y, y^=x, x^=y; //交换 if((x -= y) == 0) return y << min(i, j); //x y 相等 while((x&1) == 0) x >>= 1; //剔除2 } } int main() { int a, b; cin >> a >> b; cout << Bianary_gcd(a, b) << endl; return 0; }

最小公倍数

lcm(a, b) = a * b / gcd(a, b);

注意：a*b可能溢出，编程计算时应写成：lcm(a,b) = a / gcd(a, b) * b;