Proficient.
Put your skills to the test.

Problem summary

Two nonempty piles initially contain A and B balls. A move removes balls from one or both piles, but the ratio of the smaller removal to the larger removal must differ from the initial smaller-pile/larger-pile ratio. This forbidden ratio never changes. Count the first moves that force a win under optimal play.

Source clarification. The formula follows the official game-invariant analysis: https://infos.infosbg.com/files/Contests/ETI/2019/B/analyses/B4_arelgame_analysis.docx

Constraints

1 ≤ A,B ≤ 10^18.

Worked example

Original statement sample.

6 18

2

Solution analysis

1. Sort the initial piles so A≤B. If a move leaves a nonzero position with a different pile ratio, the opponent immediately removes everything legally. Consequently a winning move must leave the original ratio. Keeping the same orientation would require removing balls in that forbidden ratio, so the two pile roles must swap.
2. Let g=gcd(A,B), a=A/g and b=B/g. For A<B, a candidate leaves kb balls in the initially smaller pile and ka in the initially larger pile. It fits exactly when kb≤A. The opponent cannot make another ratio-preserving swap precisely when ka<b; otherwise that opponent can leave the primitive reversed pair and win.
3. Therefore count positive k satisfying k≤A/b and k≤(b−1)/a. For6,18, a=1,b=3: k can be1 or2. The resulting piles are(3,1) and(6,2), giving two winning moves. Equal initial piles admit no legal ratio-preserving move and have answer0.

Why it works

Any move leaving a different ratio loses immediately to the all-balls move. At the original ratio, only swapped multiples of the coprime pair can be reached legally. Such a position is losing exactly when its smaller pile cannot hold the primitive larger component b: it has no legal ratio-preserving reply. All other ratio positions can move directly to that primitive losing position. The two inequalities enumerate exactly the reachable losing positions.

Watch out. The forbidden ratio is fixed at the start, not recomputed after each move. Reversing the pile roles matters. Use (b−1)/a for the strict inequality and 64-bit integers for inputs and answer.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<numeric>
using namespace std;
int main(){
    long long first,second;
    cin>>first>>second;
    if(first>second){
        swap(first,second);
    }
    if(first==second){
        cout<<0<<'\n';
        return 0;
    }
    long long divisor=gcd(first,second);
    long long small=first/divisor;
    long long large=second/divisor;
    // Remaining piles are (k*large, k*small), with k*small < large.
    cout<<min(first/large,(large-1)/small)<<'\n';
}