Revise paste X-магическая пара

Решение этой задачи основано на алгоритме нахождения 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;
}