I attend the summer qualification round by inzva at algoleague. There is a problem called 'common shift', (problem link: https://algoleague.com/contest/algorithm-competition-summer-camp-2026-qualification-round/problem/common-shift/detail)
this is my code:
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)









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.
thank you so much I got the idea!