求两个正整数的最大公约数 - 辗转相除法、更相减损术和移位结合

解法一：辗转相除法\n\n辗转相除法又称为欧几里德算法，是求两个正整数的最大公约数的一种方法。该算法基于一个定理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。\n\n具体步骤如下：\n1. 初始化变量 a 和 b，将较大的数赋值给 a，将较小的数赋值给 b。\n2. 循环计算 a 和 b 的余数，直到 b 等于 0，此时 a 即为最大公约数。\n\n时间复杂度分析：设 m 和 n 的位数分别为 i 和 j，每次迭代的操作数是 O(j)。所以，总的时间复杂度是 O(i+j)。\n\n解法二：更相减损术\n\n更相减损术是求两个正整数的最大公约数的另一种方法。该方法基于一个定理：两个整数的最大公约数等于它们的差的最大公约数。\n\n具体步骤如下：\n1. 如果 m 等于 n，则 m 或 n 即为最大公约数。\n2. 如果 m 大于 n，则将 m 减去 n，得到新的 m。\n3. 如果 n 大于 m，则将 n 减去 m，得到新的 n。\n4. 重复步骤 1-3，直到 m 等于 n。\n\n时间复杂度分析：设 m 和 n 的位数分别为 i 和 j，每次迭代的操作数是 O(i+j)。所以，总的时间复杂度是 O(i+j)。\n\n解法三：辗转相减法和移位结合\n\n辗转相减法和移位结合是求两个正整数的最大公约数的一种更高效的方法。\n\n具体步骤如下：\n1. 如果 m 和 n 均为偶数，则将 m 和 n 同时右移 1 位，即 m = m >> 1，n = n >> 1。\n2. 如果 m 是偶数，n 是奇数，则将 m 右移 1 位，即 m = m >> 1。\n3. 如果 m 是奇数，n 是偶数，则将 n 右移 1 位，即 n = n >> 1。\n4. 如果 m 和 n 都是奇数，则执行更相减损术，即将较大的数减去较小的数，得到新的差值，然后继续执行步骤 1-4。\n5. 重复步骤 1-4，直到 m 等于 n。\n\n时间复杂度分析：设 m 和 n 的位数分别为 i 和 j，每次迭代的操作数是 O(log(max(m,n)))。所以，总的时间复杂度是 O(log(max(m,n)))。\n\n代码实现如下（以解法一为例）：\n\npython\ndef gcd(m, n):\n while n != 0:\n m, n = n, m % n\n return m\n\nm, n = map(int, input().split())\nresult = gcd(m, n)\nprint(result)\n