标签（空格分隔）： 算法 算法竞赛
这两种算法平时经常听到，听起来也很装逼，但是我老是忘了他们的原理，今天好好想想，写下来。
更相减损法更相减损法最早起源于我国的《九章算术》，用于求两个数的最小公倍数。大意是给定两个数a,b，如果存在偶数，就将偶数以2；否则，就比较两数大小，用大数减小数，得到一个差；对差和剩下的那个小数重复该过程，直到两数相等，下一次相减结果为0，这时的数就是a和b的最大公约数。注意，去掉偶数除以2的步骤，也正确，但是加上这一步可能会让时间复杂度减少。
例如：15和12。15-12=3；12-3=9；9-3=6；6-3=3；3=3，跳出。则最大公因数是3。
算法的C/C++代码写法如下(循环实现）： int gcdgxjs(int a,int b) { while (a!=b) { if (a if (a>b) a-=b; else b-=a; } return a;) 辗转相除法
辗转相除法最早是由pgrjb发现的，也被用来求最大公约数。算法是这样的：给定两个数a，b，求a%b，如果余数非0，就继续用除数除以余数，重复该过程，直到除数为0。此时的被除数，就是最大公约数。
例如，42和12。42%12=6；12%6=0，6&0，此时的6即为最大公约数。
算法的C/C++代码写法如下（递归实现）： int gcd(int a,int b) { if (b==0) return a; gcd(b,a%b);}
上面就是这两个算法的具体实现过程。除此之外，再补充一个定理：两个正整数a，b。假设他们的最大公约数是p，最小公倍数是q，则q=a*b/p（即ab=pq）。证明很简单，多想想就好了，在此不再赘述。