mins

Mins

== include(page="template/taskheader" task_id="mins") ==

În planul $xOy$ se desenează un dreptunghi cu laturile paralele cu axele de coordonate. Coordonatele vârfurilor din stânga-jos şi dreapta-sus ale dreptunghiului sunt: $(0,0)$ şi $(c,d)$. Fie $P$ mulţimea punctelor situate în interiorul dreptunghiului, ale căror coordonate sunt numere naturale. Prin desenarea unui număr minim $m$ de segmente de dreaptă, se uneşte vârful de coordonate $(0,0)$ cu fiecare punct din mulţimea $P$. Astfel, fiecare punct din $P$ va aparţine interiorului unui segment din cele $m$ sau va fi o extremitate a unui segment din cele $m$.

În planul $xOy$ se desenează un dreptunghi cu laturile paralele cu axele de coordonate. Coordonatele vârfurilor stânga-jos şi dreapta-sus ale dreptunghiului sunt: $(0,0)$ şi $(c,d)$. Fie $P$ mulţimea punctelor situate în interiorul dreptunghiului, ale căror coordonate sunt numere naturale. Prin desenarea unui număr minim $m$ de segmente de dreaptă, se uneşte vârful de coordonate $(0,0)$ cu fiecare punct din mulţimea $P$. Astfel, fiecare punct din $P$ va aparţine interiorului unui segment din cele $m$ sau va fi o extremitate a unui segment din cele $m$.

h2. Cerinta

h2. Cerinţă

Scrieţi un program care să citească numerele naturale $c$ şi $d$, şi care să determine numărul minim $m$ de segmente de dreaptă desenate.

Fişierul de ieşire $mins.out$ va conţine o singură linie pe care se va scrie un număr natural reprezentând numărul minim $m$ de segmente de dreaptă desenate.

h2. Restricţii

h2. Restricţii şi precizări

* $c$, $d$ sunt numere naturale nenule.

* $1 ≤ c,d ≤ 5000$

* $1 ≤ c, d ≤ 1 000 000$
* Pentru $50%$ dintre teste, $c, d ≤ 5000$.
* Pentru $80%$ dintre teste, $c, d ≤ 200 000$.

h2. Exemplu

h3. Explicaţie

$c=4, d=3$. Mulţimea $P$ a punctelor de coordonate naturale, situate în interiorul dreptunghiului, este formată din $6$ puncte: ${P1,P2,P3,P4,P5,P6}$. Pentru a uni vârful $(0,0)$, din stanga-jos al dreptunghiului. Cu cele $6$ puncte sunt suficiente $m = 5$ segmente.
 

Pentru $c=4, d=3$, mulţimea $P$ a punctelor de coordonate naturale, situate în interiorul dreptunghiului, este formată din $6$ puncte: ${P1,P2,P3,P4,P5,P6}$. Pentru a uni vârful stanga-jos al dreptunghiului, $(0, 0)$ cu cele $6$ puncte sunt suficiente $5$ segmente.
 
!problema/mins?mins.bmp!

== include(page="template/taskfooter" task_id="mins") ==

4086