这题简单，学过求最大公因数的都知道辗转相除法，肯定比相减快多了

题面大意 给你两个数字，a,ba,ba,b 每次用较大的数去减去较小的数，如果 a>ba > ba>b 那么$ a = a - b $, bbb不变。 如果两个数字相等，例a−ba-ba−b或b−ab-ab−a皆符合，直到有一个数字小于等于0，就停止运算。 题意分析 问多少次后会停止运算 解题思路 这个操作过程与辗转相减是一样的 如果每次用减法去模拟，当两个数值相差很大时，就要运算很久，我们可以直接用除法去代替减法。 嗯，如果变成除法的话，这与辗转相除法相同。 时间复杂度解析 复杂度与辗转相除法的复杂度等同，O(log max(a,b))O(log \ max(a,b))O(log max(a,b)) 代码演示

这道题很简单，轻松模拟一下就可以，连我这个小白都做得出来

#include <iostream> using namespace std; int a, b, ans; void recursion(int a, int b){ if (a <= 0 || b <= 0) return ; ans ++; if (a > b) recursion(a - b, b); else recursion(b - a, a); } signed main(){ cin >> a >> b; if (a < b) swap(a, b); ans += a / b; a = a - b * (a / b); recursion(a, b); cout << ans << endl; return 0; }