资讯详情

int gcd(int u, int v)            
{while (v != 0) {  // 循环条件：余数不为0时继续迭代int temp = v; // 步骤1：保存当前的除数vv = u % v;    // 步骤2：计算新余数（u除以v的余数）u = temp;     // 步骤3：把原来的除数v赋值给u（作为下一轮的被除数）}return u; // 余数为0时，u就是最大公约数
}

利用了gcd(a, b) = gcd(a, b % a) (其中b > a)

不必考虑u和v的大小问题，因为它们能够经过一次循环自我调整为u大v小！