Ciag liczb wspolny dzielnik nie mam pomysłu

0

Co dwie głowy to nie jedna a całe forum może mieć w sekundę jakiś pomysł.

Mam problem ponieważ nie wiem jak zrobić zadanie (Linka niestety NIE MA, zadanie z książki).

Wejscie: Ciag liczb w wektorze.

Wyjscie: Pierwsza liczbe ciagu, dlugosc ciagu, wspolny dzielnik.

Nie wiem jednak jak to wydajnie zrobić. Jedyne co wymyśliłem to:

Znajdz najwieksza z liczb i wyznacz wszystkie liczby pierwsze do pierwiastka z niej. Zapisz je do wektora
Sprawdz kazda liczbe od 0..n przez ktore z wektora sie dzieli i zapisz je w strukturze.
Sprawdz strukture szukajac najdluzszego ciagu dzielnikow.

Strasznie prymitywne i nieefektowne... Ale od godziny siedzę i myślę a z moją obecną wiedzą nic wymyśleć nie mogę. Jak ktos rzuci okiem i Od razu cos wymysli bede wdzieczny za pomysl.

2

Co masz zwrócić, ilość liczb ze wspólnym dzielnikiem, czy sam ciąg? Bo jeśli masz zwrócić samą długość ciągu to najprościej zrobić to tak:

Mamy tablicę count[sqrt(max(tab)) + 1]

  1. Dla każdego elementu e z tab:
  2. Dla każdego pierwszego dzielnika d liczby e:
    1. count[d]++
  3. Wypisz max(count)
0
unsigned long long NWD(unsigned long long a,unsigned long long b)
{
   if(!a) return max(1,b);
   if(!b) return a;
   for(unsigned long long r=0;b;a=b,b=r) r=a%b;
   return a;
}

https://lmgtfy.com/?q=najwi%C4%99kszy+wsp%C3%B3lny+dzielnik+wikipedia

0

Zwróć uwagę na następującą zależność:

NWD(a, b, ...) = NWD(NWD(a, b), ...)

1 użytkowników online, w tym zalogowanych: 0, gości: 1