最大公约数 ACM

最大公约数 ACM
两个数的最大公约数 --来源于百度空间 最大公约数最经典的算法欧几里得,下面对欧几里得算法进行基本证明,假设用f(x,y)表示x y的最大公约数,取k=x/y,b=x%y,则x=ky+b,如果一个整数能够同时整除x和y,则必能同时整除b和y,能够同时整除b和y的数也必能同时整除x和y,即x和y的最大公约数和b和y的最大公约数是相同的,即有f(x,y)=f(y,x%y)(x>=y>0),如此处理便可把原问题转化为求两个更小的...
Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录