$a$与$b$的$GCD,LCM$

辗转相除法-欧几里得算法$(gcd)$：

求两数的最大公约数；

过程：

1.不断运算$gcd$$(b$$,a$$)$;

2.因上：$a$和$b$都在减小，当$a$%$b$$=0$时，得出$ans=$ 现$b$；

3.递归后得出$gcd(a,b)=ans$;

扩展欧几里得算法：

求已知$(a,b)$，解一组$(p,q)$，使 $p*a+q*b=gcd(a,b)$;

求解过程：

1.解一定存在；

2.将问题简化，变为$b$与$a$%$b$的线性组合；

3.因上：$a$和$b$都在减小，当$b=0$时，就可得出$p=1,q=0$;

4.递归回去就可以解出$p$和$q$了；

逐步倍增法$(lcm)$：

求两数的最小公倍数；

过程：

1.不断检查$max(a,b)*i(i$为$>0$的任意正整数);

2.如果$(max(a,b)*i)$%$min(a,b)=0$,那么$i=lcm(a,b)$;

$a$和$b$的乘积：

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

原文：

# $a$与$b$的$GCD,LCM$

## 辗转相除法-欧几里得算法$(gcd)$：

求两数的最大公约数；

### 过程：

1.不断运算$gcd$$(b$$,a%b$$)$;

2.因上：$a$和$b$都在减小，当$a$%$b$$=0$时，得出$ans=$ 现$b$；

3.递归后得出$gcd(a,b)=ans$;

## 扩展欧几里得算法：

求已知$(a,b)$，解一组$(p,q)$，使 $p*a+q*b=gcd(a,b)$;

### 求解过程：

1.解一定存在；

2.将问题简化，变为$b$与$a$%$b$的线性组合；

3.因上：$a$和$b$都在减小，当$b=0$时，就可得出$p=1,q=0$;

4.递归回去就可以解出$p$和$q$了；

## 逐步倍增法$(lcm)$：

求两数的最小公倍数；

### 过程：

1.不断检查$max(a,b)*i(i$为$>0$的任意正整数);

2.如果$(max(a,b)*i)$%$min(a,b)=0$,那么$i=lcm(a,b)$;

#### $a$和$b$的乘积：

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