Language: C++

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
#define forn(a, e) for (i64 a = 0; a < (i64)(e); a++)
#define forr(a, s, e) for (i64 a = s; a < (i64)(e); a++)
#define fore(e, a) for (auto& e : a)

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; fore(e, a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; fore(e, a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; fore(r, a) { fore(e, r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; fore(e, a) { cerr << e.field << " ";} cerr << "\n"; }
#define logvff(a, f1, f2) {cerr << #a".{"#f1 << ", "#f2 << "} = \n"; fore(e, a) { cerr << "(" << e.f1 <<", " << e.f2 << ") ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logvff(a, f1, f2)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

using iip = pair<int, int>;
using llp = pair<i64, i64>;
using ivec = vector<int>;
using llvec = vector<i64>;
using svec = vector<string>;
template<typename T> using vec = vector<T>;

template<typename T, typename Dim>
auto make_vec(T value, Dim dim) { return vector<T>(dim, value); }
template<typename T, typename Dim1, typename... Dim>
auto make_vec(T value, Dim1 dim1, Dim... dims) { return make_vec(make_vec(value, dims...), dim1); }

template<typename T>
bool uax(T& v, const T& newv) { if (v < newv) { v = newv; return true; } else return false; }
template<typename T>
bool uin(T& v, const T& newv) { if (v > newv) { v = newv; return true; } else return false; }

template<typename T>
istream& operator>>(istream& is, vector<T>& c) { for (auto& e : c) is >> e; return is; }
template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& c) { for (auto& e : c) is >> e; return is; }

template<typename ...T>
istream& read(T&... args) { return (cin >> ... >> args); }

static mt19937 rande(123123);
template<typename T>
T rand_int(T from, T to) { uniform_int_distribution<T> distr(from, to); return distr(rande); }

// const i64 INF = 1e18;
const int INF = 2e9;
const i64 M = 998244353;
const int MXB = 20;
using bin = bitset<MXB + 1>;

__int128_t abs(__int128_t x) {
    if (x < 0) {
        return -x;
    } else {
        return x;
    }
}

__int128_t gcd (__int128_t a, __int128_t b, __int128_t & x, __int128_t & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	__int128_t x1, y1;
	__int128_t d = gcd (b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

bool find_any_solution (__int128_t a, __int128_t b, __int128_t c, __int128_t & x0, __int128_t & y0, __int128_t & g) {
	g = gcd (abs(a), abs(b), x0, y0);
	if (c % g != 0)
		return false;
	x0 *= c / g;
	y0 *= c / g;
	if (a < 0)   x0 *= -1;
	if (b < 0)   y0 *= -1;
	return true;
}

void shift_solution (__int128_t & x, __int128_t & y, __int128_t a, __int128_t b, __int128_t cnt) {
	x += cnt * b;
	y -= cnt * a;
}

__int128_t find_all_solutions (__int128_t a, __int128_t b, __int128_t c, __int128_t minx, __int128_t maxx, __int128_t miny, __int128_t maxy) {
	__int128_t x, y, g;
	if (! find_any_solution (a, b, c, x, y, g))
		return 0;
	a /= g;  b /= g;

	__int128_t sign_a = a>0 ? +1 : -1;
	__int128_t sign_b = b>0 ? +1 : -1;

	shift_solution (x, y, a, b, (minx - x) / b);
	if (x < minx)
		shift_solution (x, y, a, b, sign_b);
	if (x > maxx)
		return 0;
	__int128_t lx1 = x;

	shift_solution (x, y, a, b, (maxx - x) / b);
	if (x > maxx)
		shift_solution (x, y, a, b, -sign_b);
	__int128_t rx1 = x;

	shift_solution (x, y, a, b, - (miny - y) / a);
	if (y < miny)
		shift_solution (x, y, a, b, -sign_a);
	if (y > maxy)
		return 0;
	__int128_t lx2 = x;

	shift_solution (x, y, a, b, - (maxy - y) / a);
	if (y > maxy)
		shift_solution (x, y, a, b, sign_a);
	__int128_t rx2 = x;

	if (lx2 > rx2)
		swap (lx2, rx2);
	__int128_t lx = max (lx1, lx2);
	__int128_t rx = min (rx1, rx2);

    // logss(lx, rx);
    // logss(a, b);
    return lx;
	// return (rx - lx) / abs(b) + 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    rande.seed(chrono::steady_clock::now().time_since_epoch().count());
    i64 n;
    while (read(n)) {
        auto check = [&](i64 a, i64 b) {
            __int128_t r1 = find_all_solutions(2 * a, -b, 1, 1, 1e18, 1, 1e18);
            __int128_t r2 = find_all_solutions(a, -2 * b, 1, 1, 1e18, 1, 1e18);
            __int128_t r3 = find_all_solutions(2 * b, -a, 1, 1, 1e18, 1, 1e18);
            __int128_t r4 = find_all_solutions(b, -2 * a, 1, 1, 1e18, 1, 1e18);
            __int128_t ans = 1e18;
            if (r1 > 0) {
                uin(ans, 2 * r1 * a - 1);
            }
            if (r2 > 0) {
                uin(ans, a * r2 - 1);
            }
            if (r3 > 0) {
                uin(ans, 2 * b * r3 - 1);
            }
            if (r4 > 0) {
                uin(ans, b * r4 - 1);
            }
            return ans;
        };

        i64 ans = 2e18;
        for (i64 i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                uin<i64>(ans, check(i, n / i));
            }
        }
        cout << ans << endl;
    }
}

Compiler output:
a.cc: In function 'bool find_any_solution(__int128, __int128, __int128, __int128&, __int128&, __int128&)':
a.cc:89:21: error: call of overloaded 'abs(__int128&)' is ambiguous
   89 |         g = gcd (abs(a), abs(b), x0, y0);
      |                  ~~~^~~
In file included from /usr/include/c++/14/cstdlib:79,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:42,
                 from a.cc:2:
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:68:12: note: candidate: '__int128 abs(__int128)'
   68 | __int128_t abs(__int128_t x) {
      |            ^~~
In file included from /usr/include/c++/14/cstdlib:81:
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
a.cc:89:29: error: call of overloaded 'abs(__int128&)' is ambiguous
   89 |         g = gcd (abs(a), abs(b), x0, y0);
      |                          ~~~^~~
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:68:12: note: candidate: '__int128 abs(__int128)'
   68 | __int128_t abs(__int128_t x) {
      |            ^~~
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~