include <bits/stdc++.h>

using namespace std;

define int long long

define endl '\n'

define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

const int MOD = 1e9 + 7, LINF = 4e18, N = 2e5 + 5;

ifdef LOCAL

include "debug.h"

else

define debug(...) 42

endif

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void solve() { int x, y; cin >> x >> y; int a, b; a = min(x, y); b = max(x, y); int dif = abs(a — b); if (dif == 1) { cout << -1 << endl; return; } if(a==1 && b==1){ assert(1>2); }

if (gcd(a, b) > 1) {
    cout << 0 << endl;

    return;
}
if (a % 2 == 1 && b % 2 == 1) {
    cout << 1 << endl;
    //  assert(1 > 2);
    return;
}

if (gcd(a, b) > 1) {
    cout << 0 << endl;

    return;
}

cout << ((a + dif) / dif) * dif - a << endl;

}

signed main() { fastio; int t = 1; // cin >> t;

while (t--) {
    solve();
}

cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

return 0;

}

I couldn't prove/disprove this solution. Is there anyone help me to prove or disprove. (Btw I got AC but I think it is about test cases)

Comments (2)

Write comment?

montes332

71 minute(s) ago, hide # |

your last branch is wrong in general. the formula ((a + dif) / dif) * dif — a finds the smallest k ≥ 1 such that dif | (a+k), but the optimal k comes from the smallest prime divisor of dif, not dif itself. counter-example: a=4, b=19, dif=15. min prime divisor is 3, so k=2 works (gcd(6, 21)=3). your code outputs 11. another one: a=2, b=11, dif=9. k=1 gives gcd(3, 12)=3. your code outputs 7. so if you got AC because of weak tests (probably most tests have dif prime, or fall into earlier branches). the "both odd — 1" branch is correct btw, but it's actually a special case of the general rule (smallest prime of dif is 2 when both odd). correct approach: factorize dif, for each prime p take (p — a%p) % p, output the min. the "both odd" case stays as a fast path but isn't strictly needed.

→ Reply