OI X - kaf (Speedrun)

// https://szkopul.edu.pl/problemset/problem/1mRVaDVJ8FN2x69FUiYf89yt/site/?key=statement

#include <bits/stdc++.h>

using BI = std::vector<int>;

BI s2b(std::string s) {
    BI n;
    if (s.empty()) {
        n.push_back(0);
        return n;
    }
    for (int i = s.size() - 1; i >= 0; i--)
        n.push_back(s[i] - '0');
    while (n.size() > 1 && n.back() == 0)
        n.pop_back();
    return n;
}

void print(BI n) {
    if (n.empty()) {
        std::cout << 0;
        return;
    }
    for (int i = n.size() - 1; i >= 0; i--)
        std::cout << n[i];
    std::cout << "\n";
}

bool isZero(const BI& n) {
    return n.size() == 1 && n[0] == 0;
}
bool isEven(const BI& n) {
    return n.empty() || n[0] % 2 == 0;
}

bool isLess(const BI& a, const BI& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; i--)
        if (a[i] != b[i]) return a[i] < b[i];
    return false;
}

void div2(BI& n) {
    int rem = 0;
    for (int i = n.size() - 1; i >= 0; i--) {
        int val = n[i] + rem * 10;
        n[i] = val / 2;
        rem = val % 2;
    }
    while (n.size() > 1 && n.back() == 0)
        n.pop_back();
}

void sub(BI& a, const BI& b) {
    int bor = 0;
    for (int i = 0; i < a.size(); i++) {
        int val = a[i] - bor - (i < b.size() ? b[i] : 0);
        if (val < 0) {
            val += 10;
            bor = 1;
        } else
            bor = 0;
        a[i] = val;
    }
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
}

void add(BI& a, const BI& b) {
    int car = 0;
    for (int i = 0; i < std::max(a.size(), b.size()) || car; i++) {
        if (i == a.size()) a.push_back(0);
        int sum = a[i] + car + (i < b.size() ? b[i] : 0);
        a[i] = sum % 10;
        car = sum / 10;
    }
}

BI gcd(BI u, BI v) {
    if (isZero(u)) return v;
    if (isZero(v)) return u;
    int shift = 0;
    while (isEven(u) && isEven(v)) {
        div2(u);
        div2(v);
        shift++;
    }
    while (isEven(u))
        div2(u);
    while (!isZero(v)) {
        while (isEven(v))
            div2(v);
        if (isLess(v, u)) swap(u, v);
        sub(v, u);
    }
    while (shift--)
        add(u, u);
    return u;
}

void solve() {
    std::string ns, ks, ls;
    std::cin >> ns >> ks >> ls;
    BI n = s2b(ns), k = s2b(ks), l = s2b(ls);

    if (isLess(l, k)) swap(k, l);

    BI G = gcd(k, l);

    BI rhs = l;
    add(rhs, k);
    sub(rhs, G);

    if (!isLess(n, rhs)) {
        print(G);
    } else {
        BI B = n;
        sub(B, l);
        BI A = k;
        sub(A, B);
        print(A);
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}