Решение этой задачи основано на алгоритме нахождения GCD.

Сначала давайте попытаемся решить ее наивно. Будем поддерживать условие, что 𝑎>𝑏
. Если это не так, давайте поменяем 𝑎
и 𝑏
местами. Для начала, если 𝑏>𝑎−𝑏
, давайте присвоим 𝑏:=𝑎−𝑏
. Окей, теперь давайте вычитать 𝑏
из 𝑎
до тех пор, пока не выполнится 𝑏≥𝑎−𝑏
, а затем будем повторять этот алгоритм, пока не станет 𝑎=0
или 𝑏=0
. Если после какого-то шага мы получим 𝑎=𝑥
или 𝑏=𝑥
, то мы закончили и ответ равен YES. Если 𝑎=0
или 𝑏=0
, а мы не получили 𝑥
, то ответ равен NO.

Окей, мы можем заметить, что мы всегда вычитаем минимально возможное 𝑏
из 𝑎
и пытаемся поддерживать это условие. Можно доказать, что такой алгоритм получает все возможные числа, которые в принципе могут быть получены любой последовательностью операций из условия задачи (либо в 𝑎
, либо в 𝑏
).

Теперь нам необходимо каким-то образом ускорить это решение. Очевидно, большинство операций бесполезны для нас в этой конкретной задаче. Первая часть заключается в том, что мы можем пропускать все операции до тех пор, пока 𝑏
не станет больше, чем 𝑎−𝑏
. Количество таких операций равно ⌊𝑎−𝑏2𝑏⌋
. А вторая часть заключается в том, что мы можем пропускать все операции до тех пор, пока мы не получим 𝑥
в 𝑎
. Количество таких операций равно ⌊𝑎−𝑥𝑏⌋
. Для простоты эту часть можно также записать как ⌊𝑎−𝑥2𝑏⌋
. Это не особо замедлит наше решение, но формула для финального количества операций, которые мы пропускаем, станет немного проще. Это количество равно 𝑐𝑛𝑡=𝑚𝑎𝑥(1,⌊𝑎−𝑚𝑎𝑥(𝑏,𝑥)2𝑏⌋)
(фактически, мы берем минимум из тех двух величин, которые мы описали выше, потому что мы не хотим пропустить ни один из этих случаев). Таким образом, мы преобразуем пару (𝑎,𝑏)
в пару (𝑎−𝑏∗𝑐𝑛𝑡,𝑏)
и продолжаем этот алгоритм.

Также существуют более простые подходы, использующие эту же идею в более красивом виде.

Асимптотика решения: 𝑂(log𝑎)
на набор тестовых данных.

#include <bits/stdc++.h>

using namespace std;

bool get(long long a, long long b, long long x) {
if (a == x || b == x) return true;
if (a < b) swap(a, b);
if (b > a - b) b = a - b;
if (x > max(a, b) || a == 0 || b == 0) return false;
long long cnt = max(1ll, (a - max(x, b)) / (2 * b));
return get(a - b * cnt, b, x);
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
long long a, b, x;
cin >> a >> b >> x;
if (get(a, b, x)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}

return 0;
}