Moisil++ 2023 Clasele 7-8 Mirror | Cătălin și masa cuantică de biliard

Cerință

Cătălin are o masă cuantică de biliard de dimensiuni $n \times m$.

Inițial se află o bilă în colțul stânga-jos a mesei, la coordonatele $(0,0)$. În fiecare secundă, bila se va mișca de la poziția curentă $(x,y)$ la $(x+1,y+1)$.

În plus, când bila se ciocnește de o margine a mesei, atunci ea se va teleporta pe latura opusă, păstrându-și direcția:

• Dacă bila se ciocnește de marginea de sus a mesei la coordonatele $(x,n)$, atunci ea se va teleporta instantaneu pe marginea de jos la coordonatele $(x,0)$.
• Dacă bila se ciocnește de marginea din dreapta a mesei la coordonatele $(m,y)$, atunci ea se va teleporta instantaneu pe marginea din stânga la coordonatele $(0,y)$.

Aflați prima secundă când bila va ajunge în colțul din dreapta-sus a mesei de biliard. Se garantează că acest lucru mereu este posibil.

Date de intrare

Pe prima linie a fișierului de intrare biliard.in se vor afla două numere $n$ și $m$, dimensiunile mesei de biliard.

Date de ieșire

Fișierul de ieșire biliard.out va conține un număr, prima secundă când bila va ajunge în colțul din dreapta-sus a mesei de biliard.

Restricții și precizări

• $1 \le n,m \le 10^9$;
• Pentru $5$ puncte, $n=1$;
• Pentru încă $10$ puncte, $n=2$;
• Pentru încă $20$ de puncte, $n,m \le 1 \ 000$;
• Pentru încă $25$ de puncte, $n,m \le 10^6$;
• Pentru restul de $40$ de puncte, nu se impun restricții suplimentare.

Exemplul 1

biliard.in

4 6

biliard.out

12

Explicație

Bila va avea următorul traseu:

• $(0,0) \xrightarrow{1s} (1,1) \xrightarrow{1s} (2,2) \xrightarrow{1s} (3,3) \xrightarrow{1s} (4,4) \xrightarrow{0s}$ tp la $(4,0)$
• $(4,0) \xrightarrow{1s} (5,1) \xrightarrow{1s} (6,2) \xrightarrow{0s}$ tp la $(0,2)$
• $(0,2) \xrightarrow{1s} (1,3) \xrightarrow{1s} (2,4) \xrightarrow{0s}$ tp la $(2,0)$
• $(2,0) \xrightarrow{1s} (3,1) \xrightarrow{1s} (4,2) \xrightarrow{1s} (5,3) \xrightarrow{1s} (6,4)$

Pentru a ajunge în colțul din dreapta-sus a mesei, bila a avut nevoie de $4+2+2+4=12$ secunde.

Exemplul 2

biliard.in

917 980

biliard.out

128380

Exemplul 3

biliard.in

957423 560507

biliard.out

31567193733