Question

一道编程问题

一道编程问题学渣求解这套程序的后半段从r=m Mod n开始程序是在求一个什么数学意义上的数？过程中数字是怎么切换的，比如说:
m=4 n=3
t=m=4
m=n=3
n=t=4
最后 n=4 m=3了

Answer 1

r = m mod n 的意思是求余数，比如 5 mod 2 = 1 因为5/2 余数为1，而5 mod 5 = 0即为能除尽，而 3 mod 7 = 3 因为3/7 = 0 余 3
接下来的loop是在用欧几里得算法算两个数的最大公约数。

a和b的最大公约数是a和b都能除尽的最大的数，ie最大的x st a mod x =0 and b mod x = 0。比如8和12的最大公约数是4
看code：
当m>n时，如果 r = m mod n 为0，那么n就是最大公约数，比如25 mod 5=0最大公约数为5, 16 mod 8=0最大公约数为8

如果r 不是0， 比如r=12 mod 8 = 4，进入loop，那设置新的m=8, n=4, 得到 r = 8 mod 4 = 0, 结束loop。n=4是12和8之间的最大公约数
再看 如果是9和5之间，r = 9 mod 5 = 4, 进入loop，新的m=5, n = 4, 得到r = 5 mod 4 = 1 r仍然不是0，那再loop，设新的m = 4, n = 1, 得到r = 4 mod 1 = 0. 结束loop。得到9和5的最大公约数是n=1。

所以，只有当r=0, 即r不再>0时，loop结束，此时的n，为最大公约数。

最小公倍数 是 一个数x，它是最小的，能同时除尽a和b 的数。比如(12,8)的最小公倍数 = 24 = 12*8/4, 此处4是12和8的最大公约数。

所以有了最大公约数(gcd)，可以计算最小公倍数为：x=a*b/gcd(a,b)
所以最下方是通过求出的最大公约数n, 原本的ml和nl, 算出最小公倍数：ml*nl/n

可以百度一下最大公约数，最小公倍数，余数的概念哦，属于代数基础。