Solution for https://codeforces.com/contest/1152/problem/C

neko_does_maths.cc

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr ll p = 1000000007;


ll gcd(ll a, ll b) {
    while(b) {
        ll tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}


ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}


ll fast_pow(ll base, ll pow, ll mod) {
    base %= mod;
    if(base == 0) return 0ll;

    ll ret = 1ll;
    while(pow) {
        if(pow & 1ll == 1ll) ret = (ret * base) % mod;
        base = (base * base) % mod;
        pow >>= 1;
    }

    return ret;
}


bool miller_rabin_test(ll n, ll precision=10) {
    if(n == 1) return false;
    if(n & 1ll == 0) return n == 2;
    if(n == 3 || n == 5 || n == 7) return true;

    random_device seed;
    mt19937 gen(seed());
    uniform_int_distribution<ll> randll(2, n - 2);

    ll s = 0, d = n - 1;
    while(d & 1ll == 0) {
        s++;
        d >>= 1;
    }

    while(precision--) {
        ll a = randll(gen);
        ll x = fast_pow(a, d, n);
        if(x == 1 || x == n - 1) continue;
        bool a_good = false;
        for (int i = 0; i < s - 1; ++i) {
            x = (x * x) % n;
            if(x == 1) return false;
            else if(x == n - 1) {
                a_good = true;
                break;
            }
        }
        if(!a_good) return false;
    }

    return true;
}


vector<ll> get_primes(ll n) {
    vector<ll> ret, lp(n + 1, 0);

    for (int i = 2; i <= n; ++i) {
        if(lp[i] == 0) {
            lp[i] = i;
            ret.emplace_back(i);
        }

        for(int j = 0; j < ret.size() && ret[j] < lp[i] && i * ret[j] <= n; j++) {
            lp[i * ret[j]] = ret[j];  
        }
    }

    return ret;
}


vector<pair<ll, ll>> get_factors(ll n) {
    vector<ll> primes = get_primes(100000);
    vector<pair<ll, ll>> ret;

    for(const auto &prime : primes) {
        if(n % prime != 0) continue;
        ll count = 0;
        while(n % prime == 0) {
            count++;
            n /= prime;
        }
        ret.emplace_back(prime, count);
        if(n == 1) break;
    }

    if(miller_rabin_test(n)) {
        ret.emplace_back(n, 1);
    }

    return ret;
}


void _rec_divisors(ll val, ll index, const vector<ll> &base, const vector<ll> &exp, vector<ll> &coll) {
    if(index == base.size()) {
        coll.emplace_back(val);
        return;
    }

    ll curr = 1ll;
    for (int i = 0; i <= exp[index]; ++i) {
        _rec_divisors(val * curr, index + 1, base, exp, coll);
        curr *= base[index];
    }
}


vector<ll> get_divisors(ll n) {
    if(n == 1) return vector<ll>(1, 1);
    auto factors = get_factors(n);
    ll l = factors.size();
    vector<ll> ret, base(l), exp(l);
    for (int i = 0; i < l; ++i) {
        base[i] = factors[i].first;
        exp[i] = factors[i].second;
    }
    _rec_divisors(1ll, 0ll, base, exp, ret);
    return ret;
}


int main() {
    ll a, b;
    cin >> a >> b;
    if(a > b) swap(a, b);
    ll bk = 0, blcm = lcm(a, b), k = 1;
    if(b - a == 0) {
        cout << 0 << endl;
        return 0;
    }
    vector<ll> divisors = get_divisors(b - a);
    for(const auto &div : divisors) {
        k = div - a % div;
        ll clcm = lcm(a + k, b + k);
        if(clcm < blcm || clcm == blcm && k < bk) {
            blcm = clcm;
            bk = k;
        }
    }
    cout << bk << endl;
    return 0;
}