Solução Intermediário Informática - Semana 44

Solução de Frederico Bulhões

Para resolver esse problema, devemos usar a propriedade MDC(a,b,c) = MDC(a, MDC(b, c)). A partir disso podemos simplismente usar o Algoritmo de Euclidese computar sequencialmente o MDC de todos os valores das posições entre 1 a N.

Código para melhor entendimento:


// solucao de Davi Gabriel
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if(b == 0) return a;
if(a == 0) return b;
int x = min(a, b);
int y = max(a, b);
return gcd(x, y%x);
}
int num[100100];
int main() {
int n, mdc = 0;
cin >> n;
for(int i = 0; i < n; i++){
cin >> num[i];
mdc = gcd(mdc, num[i]);
}
cout << mdc << "\n";
}

view raw

mdc.cpp

hosted with ❤ by GitHub