更相減損法求最大公約數原理

更相減損法求最大公約數的原理是基於輾轉相減法。具體來說，兩個數不斷進行減法運算，直到其中一個數變為0為止。在這個過程中，每次操作都會保留剩餘的那個數，直到其中一個數變為0。這個過程可以用以下步驟來描述：

1. 將兩個數a和b中的較小數記為r，將另一個數記為a'。
2. 將a'和b都減去r，得到新的兩個數a''和b''。
3. 重複步驟2，直到a''變為0為止。
4. 此時，b就是最大公約數。

更相減損法的原理在於，每次操作都會將較大的數不斷減小，直到其中一個數變為0為止。在這個過程中，每次操作都會保留剩餘的那個數，因此最終得到的結果就是兩個數的最大公約數。這個方法的時間複雜度是O(log n)，其中n是兩個數的乘積。這是因為每次操作都會將較大的數減小一半，所以需要進行log n次操作。