C++, DAM NAJ JAK BĘDZIE DO SOBOTY 29.04
Na wejściu dany jest n-elementowy ciąg liczb całkowitych. Twoim zadaniem jest znalezienie największego
wspólnego dzielnika tego ciągu.
Wejście
W pierwszym wierszu wejścia podana jest liczba n (1 ≤ n ≤ 2.5 · 105
) oznaczająca długość ciągu. W
drugim wierszu podane są liczby a1, a2, . . . , an (1 ≤ ai ≤ 109
) - elementy ciągu.
Wyjście
Podaj największy wspólny dzielnik całego ciągu podanego na wejściu.
czyli na przykład dla wejścia:
5
14 35 77 7 693
wyjściem jest 7
a dla
6
2 3 4 5 6 7
wyjściem jest 1
Na wejściu dany jest n-elementowy ciąg liczb całkowitych. Twoim zadaniem jest znalezienie największego
wspólnego dzielnika tego ciągu.
Wejście
W pierwszym wierszu wejścia podana jest liczba n (1 ≤ n ≤ 2.5 · 105
) oznaczająca długość ciągu. W
drugim wierszu podane są liczby a1, a2, . . . , an (1 ≤ ai ≤ 109
) - elementy ciągu.
Wyjście
Podaj największy wspólny dzielnik całego ciągu podanego na wejściu.
czyli na przykład dla wejścia:
5
14 35 77 7 693
wyjściem jest 7
a dla
6
2 3 4 5 6 7
wyjściem jest 1
Odpowiedź:
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int result = a[0];
for (int i = 1; i < n; i++) {
result = gcd(result, a[i]);
}
cout << result << endl;
return 0;
}
Wyjaśnienie:
Najprostszym sposobem na znalezienie największego wspólnego dzielnika ciągu liczb jest użycie algorytmu Euklidesa. Aby to zrobić, należy zacząć od dwóch liczb a i b, a następnie powtarzać poniższy krok, aż do momentu, gdy b stanie się równe 0:
Oblicz resztę dzielenia a przez b.
Przypisz wartość b do a.
Przypisz wartość reszty dzielenia do b.
Największy wspólny dzielnik a i b jest równe a, gdy b jest równe 0.
dla każdej liczby ciągu wykonujemy krok 1 algorytmu Euklidesa z poprzednią wyliczoną wartością. Na końcu otrzymujemy największy wspólny dzielnik całego ciągu.