SPOJ NWD długi czas

Question

Witam, właśnie zrobiłem to zadanie jednak martwi mnie to, że uzyskałem tak długi czas. Dużo odpowiedzi miało czasy nawet 0.0
Kod: https://ideone.com/xc3ekX
Zadanie: https://pl.spoj.com/problems/PP0501A/

Comments

Zła kategoria (SPOJ)

Answer 1

Twój algorytm wykorzystuje pętlę for idąc po kolei po liczbach i sprawdzając każdą - takie rozwiązanie jest często najprostsze ale też strasznie nieefektywne. Poczytaj sobie o algorytmie euklidesa (szczególnie tym z modulo) na wyznaczanie NWD - ten algorytm jest dużo lepszy.