Diferente pentru problema/euclid2 intre reviziile #7 si #19

Nu exista diferente intre titluri.

Diferente intre continut:

h2. Cerinta
Dandu-se doua numere naturale $a$ si $b$ sa se calculeze cel mai mare divizor comun al lor.
Dandu-se $T$ perechi de numere naturale {$(a, b)$}, sa se calculeze cel mai mare divizor comun al numerelor din fiecare pereche in parte.
h2. Date de intrare
Fisierul de intrare $euclid2.in$ contine pe prima linie doua numere naturale $a$ si $b$.
Fisierul de intrare $euclid2.in$ contine pe prima linie numarul $T$ de perechi. Urmatoarele $T$ linii contin cate doua numere naturale $a$ si $b$.
h2. Date de iesire
In fisierul de iesire $euclid2.out$ se va afisa o singura linie ce contine rezultatul cerut.
In fisierul de iesire $euclid2.out$ se vor scrie $T$ linii. A $i$-a linie din acest fisier contine cel mai mare divizor comun al numerelor din perechea de pe linia $i+1$ din fisierul de intrare.
h2. Restrictii
* $2 ≤ a, b ≤ 2 * 10^9^$
* $1 ≤ T ≤ 100 000$
* Pentru fiecare pereche, $2 ≤ a, b ≤ 2 * 10^9^$
h2. Exemplu
table(example). |_. euclid2.in |_. euclid2.out |
|12 42|6|
|3
12 42
21 7
9 10
|6
7
1|
h2. Indicatii de rezolvare
O scurta prezentare a acestui subiect gasiti 'aici':http://en.wikipedia.org/wiki/Greatest_common_divisor.
Cel mai mare divizor comun dintre doua numere $a$ si $b$ se poate calcula iterativ, printr-o simpla parcurgere a tuturor numerelor de la 2 la {$minim(a, b)$}. Aceasta rezolvare se gaseste 'aici':job_detail/142976?action=view-source si obtine 40 de puncte. Pentru a imbunatati timpul de rulare putem folosi 'algoritmul lui Euclid':http://en.wikipedia.org/wiki/Euclidean_algorithm.
O solutie de 100 de puncte, pe ideea din articolul de mai sus, o gasiti 'aici':job_detail/142977?action=view-source.
Cel mai mare divizor comun dintre doua numere $a$ si $b$ se poate calcula iterativ, printr-o simpla parcurgere a tuturor numerelor de la 2 la {$minim(a, b)$}. Aceasta rezolvare se gaseste 'aici':job_detail/153457?action=view-source si obtine 30 de puncte. Pentru a imbunatati timpul de rulare putem folosi 'algoritmul lui Euclid':http://en.wikipedia.org/wiki/Euclidean_algorithm prin 'scaderi':job_detail/153459?action=view-source, ceea ce duce la obtinerea a 60 de puncte, sau prin impartiri, 'solutie':job_detail/153481?action=view-source ce obtine punctajul maxim.
h2. Probleme similare
* 'cmmdc':problema/cmmdc de pe infoarena
== include(page="template/taskfooter" task_id="euclid2") ==
== include(page="template/taskfooter" task_id="euclid2") ==
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2759