NWD Zadanie C++

Question

Zadanie NWD kilku liczb

---

NWD dwóch liczb można obliczyć algorytmem Euklidesa. W jaki sposób wyznaczyć NWD wielu liczb? W pierwszym wierszu wejścia musi znaleźć się liczba całkowita n (1 < n < 10²), oznaczająca liczbę testów. Każdy z n-kolejnych wierszy zawiera jedną liczbę całkowitą p mniejszą niż miliard, kolejny wyraz ciągu, dla którego trzeba wyznaczyć NWD. Przyjmujemy, że wartości, z jakich chcemy policzyć NWD są liczbami całkowitymi.

---

Przykład #1

Dla danych:

3

12 20 16

poprawnym rozwiązaniem jest:

4

Answer 1

NWD(a, b, c) = NWD(NWD(a, b), c)

NWD(a, b, c, d) = NWD(NWD(a, b, c), d) = NWD(NWD(NWD(a, b), c), d)

I tak dalej dla większej liczby parametrów.

Comments

dzięki, sprobuje to zimplementowac w c++

---

udalo mi sie, dzieki:

#include<bits/stdc++.h>
using namespace std;
int nwd(long long a,long long b)
{
    while(a!=b)
    {
        if(a>b) a-=b;
        else b-=a;
    }
    return a;
}
int main()
{
    int ile; cin>>ile;
    long long a,b; cin>>a>>b;
    int gcd=nwd(a,b);
    for(int i=1; i<=ile-2; i++)
    {
        cin>>a;
        gcd=nwd(gcd,a);
    }
    cout<<gcd;
}

Answer 2

Przykład bez użycia rekurencji.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

auto findGCD( const vector<int>& numbers )
{
    auto result = *numbers.cbegin();
    for( const auto& number : numbers )
    {
        result = __gcd( number , result );
        if( result == 1 ) return 1;        
    }
    return result;
}

int main()
{    
    cout << findGCD( vector<int>{ 234,24,54,48 } ) << endl;    
}

https://godbolt.org/z/fejaqhP9E

 

 

Comments

https://en.cppreference.com/w/cpp/numeric/gcd