$O(loga)$ gcd

答案是不超过 $2$ 的，可以通过使用一对 $(0,1)$ $a$ 次和一对 $(1,0)$ $b$ 次，一定可以达到点 $(0,0)$ 的。总费用为 $2$ 。

需要检查是否有可能以 $1$ 的代价到达。由于花费是 $1$ ，我们需要找到一对 $(dx, dy)$ ，即 $dx \le k$ ， $dy \le k$ ，并且可以通过持续应用这一对到达单元格 $(0,0)$ 。这意味着存在一个整数 $t$ 使得 $a = t \cdot dx, b = t \cdot dy$ ，即 $t$ 是 $a$ 和 $b$ 的因子。

为了使 $dx, dy \leq k$ ， $t$ 越大越好, 所以 $t$ 取 $a$ 和 $b$ 的最大公约数

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

#define x first
#define y second

const int N = 2e5 + 10, mod = 1e9 + 7;


void solve()
{
    LL a, b,k;
    cin >> a >> b >> k;
    LL g = gcd(a, b);
    a /= g, b /= g;
    if(max(a, b) <= k)
        cout << 1 << endl;
    else
        cout << 2 << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
	int t = 1;
	cin >> t;
	while(t --)
		solve();
}