首先介绍一下辗转相除法：
即m 和 n求最大公因数（假设m大于n），先用 m 除以 n ，如果余数 r 为 0 ，则 n 就是最大公因数，否则，将 n 给了 m ，将 r 给了 n ，再用 m 除以 n ，如果余数 r 为 0 ，则n为最大公因数，否则重复执行上述操作，直至 r 为 0 ，此时的 n 就是 m 和 n 的最大公因数。
相信很多人包括我在内都对这个算法不理解，我今天突然有了些想法，分享给大家。
我觉的辗转相除法就是一个分块的思想，为什么这么说呢，我们通过一个例子来说明：
假设 m = 72 ，n = 48
先用 m 除以 n ，如果直接余数 r 为0，那最大公因数自然就是 n 了，这个大家都能理解，问题是72/48余数为24，这时候，我们自然可以将72分块，写成：
72 = 48+24
这个时候，72 和 48 的最大公因数就可以写成：
48+24 和 48
的最大公因数
这下是不是看起来有感觉了？
求最大公因数的中心思想就是找出两个数公有的最大的最大的那一块，那么我们就要对这两个数进行分块，分成一块一块的，其方法就是用大的数除以小的数。
48+24 和 48的最大公因数就是48+24 和 48 的最大公有的那一块，因为左边的 48 和右边的 48 相等，所以再看看从48中能否分出余数 24 那么大的“块”，于是用 48 除以24 分块，此时余数正好为0，分块结束，此时的“块”即是最大的公有“块”，那么次“块”就是最大的公因数。如果余数不为0，说明分块还没完成，需要继续往小了分。
24+24+24 和24+24
上式即是最终的分块结果。
有点啰嗦了，希望能帮到大家！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
