正经题解｜新年魔法

题面大意

给你两个数字，$a,b$

每次用较大的数去减去较小的数，如果 $a > b$ 那么$ a = a - b $, $b$不变。

如果两个数字相等，例$a-b$或$b-a$皆符合，直到有一个数字小于等于0，就停止运算。

题意分析

问多少次后会停止运算

解题思路

这个操作过程与辗转相减是一样的

如果每次用减法去模拟，当两个数值相差很大时，就要运算很久，我们可以直接用除法去代替减法。

嗯，如果变成除法的话，这与辗转相除法相同。

时间复杂度解析

复杂度与辗转相除法的复杂度等同，$O(log \ max(a,b))$

代码演示

#include <iostream>
using namespace std;
int main() {
    int a,b;
    cin >> a >> b;
    int cnt = 0 ;
    while(a > 0 && b > 0) {
        if (a < b) {
            cnt += (b / a);
            b %= a;
        } else {
            cnt += (a / b);
            a %= b;
        }
    }
    cout << cnt << endl;
    return 0;
}