Zadanie : euklid-c
Zadanie

Dana jest następująca definicja funkcji obliczającej najwiekszy wspólny dzielnik liczb całkowitych dodatnich: 

NWD(a, b) - zwróć największy wspólny dzielnik liczb a i b

1. Dopóki b jest dodatnie:
   a) r:=a mod b
   b) a:=b
   c) b:=r
2. Zwróć a

Korzystając z tak zdefiniowanej funkcji NWD możemy rekurencyjnie obliczyć największy wspólny dzielnik dowolnej ilości liczb: 

NWDX(a1, a2, ..., an) - zwróć największy wspólny dzielnik wszystkich liczb

2. Jeśli n=1, to zwróć a1 i zakończ
2. Jeśli n=2, to zwróć NWD(a1, a2) i zakończ
3. Podziel ciąg na dwie mniej więcej równe części: k:=n div 2
4. Oblicz x:=NWDX(a1, ..., ak)
5. Oblicz y:=NWDX(ak+1, ..., an)
6. Zwróć NWD(x, y)

Napisz program, który dla podanego ciągu liczb wyznaczy największy wspólny ich dzielnik podaną metodą.

Wejście

Pierwszy wiersz wejścia zawiera liczbe całkowitą n z zakresu 1..20. W wierszu drugim zapisano n liczb całkowitych z zakresu 1..109.

Wyjście

Pierwszy wiersz wyjścia powinien zawierac obliczony największy wspólny dzielnik liczb podanych na wejściu.
W wierszu drugim należy zapisać, ile razy obliczona wartość x w punkcie 4 okazała się być różna od obliczonej wartości y w punkcie 5.

Przykład

Dla danych podanych na wejściu:

8
1728 3456 144 2880 288 1728 1152 72

Poprawną odpowiedzią jest wyjście:

72
3

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath 
Limit czasu        : 0.25 s
Limit pamięci      : 32 MB
Słowa niedozwolone :