找到这个函数的循环不变量

Question

我需要找到 gcd 的循环不变量（euclid 算法），但我不知道从哪里开始或要看什么

    int f(int x, int y) {
       while (true) {
           int m = x % y;
           if(m == 0) return y;
           x = y;
           y = m;
       }
    }

Answer 1

循环不变量是在循环的每次迭代中都满足的条件。在您的情况下，您不是在可以更改的条件下循环，因此如果循环不变量不是“循环条件始终为真”，则每次迭代唯一适用的另一件事是“m 的值始终显示 x 是否可以被 y 整除。

Answer 2

x 和 y 的最大公约数在整个循环中保持不变。因此，循环不变量是 gcd(x,y) = c 其中 c 是常数。