基于C++求两个数的最大公约数最小公倍数

求x,y最大公约数的函数如下：

int gys(int x,int y)
{ int temp;
while(x)
{temp=x;
x=y%x;
y=temp;}
return y;
}

x=y的时候一目了然下面就不考虑，仅针对x不等于y的情况.在程序执行的某次循环过程中，若x>y，那这次循环仅换成了x和y数值的交换。这一点很关键。假设x,y的最大公约数为m。我们想办法来表示两者：那么有三种情况(i,j均为大于等于0的整数)

            1）x=m*(2i+1)   y=m*(2i+1)(此种情况i不等于j)
            2）x=m*(2i+1)   y=m*2j
            3）x=m*2i       y=m*(2j+1)

发生有效循环时(这里的有效循环定义为除x,y交换数值循环外的循环，即x和y的数值至少有一个发生改变)。

(1)若是第一种表示，因为执行x=y%x时x<y(即i<j)(注意若输入的x>y，则发生有效循环时已经完成交换)，那么这次循环执行完的时候 x=m*2(j-i),y=m*(2i+1)，即此时可以认为x=m*偶数,y=m*奇数，那么由于（偶数-奇数=奇数）且（奇数-偶数=奇数），那么每执行一次有效循环(注意执行有效循环时，一定是y>x)，执行x=y%x实际做的是x=m*(若干次奇数减偶数或者偶数减奇数的的混合)，注意此时的x=m*1才会满足使x=y%x=0进而使循环终止，执行此次循环的y可以是y=m*偶数或者y=m*奇数，由于x执行前赋值给temp，故最后返回的为y=temp=m，就是最大公约数。

    (2)第二种表示和第三种表示求公约数时实际上完全同第一种表示，因为只要是x,y为正整数且最大公约数为m，那么只要m*(2i+1),m*(2j+1),m*2(j-i)(或m*2(i-j))都大于0(此种情况i不等于j)，最大公约数也是m。
     例如若能表示成x=m*(2i+1)   y=m*2j，他们的最大公约数和x=m*(2i+1)   y=m*(2(i+j)+1)是一样的，这可以写成第一种表示方法嘛，第三种表示也是一目了然的依次类推。

这种方法也可以用来求x,y的最小公倍数，众所周知，最小公倍数==x*y/最大公约数

简而言之。利用欧几里得辗转相除法。gcd(a,b)=gcd(b,a%b);