**假设把x和y的最大公约数表示成为f(x,y)
f(x,y) = f(y,x%y) **
/* 用欧几里德算法求最大公约数
* 求最大公约数是一个比较基础的问题,
* 欧几里得早在《几何原本》中就阐明了一个高效的算法,
* 据说这大概发生在公元前300年左右。
* 具体是这样的:假设把x和y的最大公约数表示成为f(x,y),
* 并且x>=y>0。现在取k=x/y,b=x%y,则x=k*y+b,
* 变形为b=x - k*y;x和y能被f(x,y)整除,那么b也能被f(x,y)整除;
* 所以 f(x,y) = f(y,x%y)
*/
int GCD(int x,int y)
{
return (!y) ? x : GCD(y,x%y);
}
网友评论