(KOD W ŚRODKU) Przekroczono limit czasu w SPOJ, optymalizacja krótkiego programu

Question

Starałem się jak mogłem, ale nie potrafię bardziej zoptymalizować tego zapisu, może ktoś poda mi to, co mi umknęło? Algorytm dotyczy zadania http://pl.spoj.com/problems/PRZEDSZK/

#include <iostream>
using namespace std;
int zestawy, g1, g2, iloczyn;
int main()
{
    cin>>zestawy;
    for(int i=1; i<=zestawy; i++){
        cin>>g1>>g2;
        iloczyn=g1*g2;
        do{
            if(g1>g2) g1=g1-g2;
            else g2=g2-g1;
        }while(g1!=g2);
        cout<<iloczyn/g1<<endl;
    }
}

Z góry dziękuję i pozdrawiam.

Answer 1

do
{
            if(g1>g2) g1=g1-g2;
            else g2=g2-g1; //tutaj jest źle

 }while(g1!=g2);

Powinno być else if(g1<g2), ponieważ else działa dla każdego innego przypadku, masz ifa (g1>g2), ale jeżeli g1 będzie równe g2, to nadal będziesz odejmować. Po poprawieniu tego ifa dostałem AC.

Answer 2

Tak właściwie problem polega na tym, że gdy masz przypadek g1 == g2 program zapętla się. Uwzględnij dodatkowego else if, albo zamień pętlę na while (z tym samym warunkiem).

Answer 3

1) Źle otagowałeś swoje pytanie. Powinno się znaleźć w kategorii "SPOJ".

2) Wstaw kod w odpowiednie znaczniki. https://forum.pasja-informatyki.pl/faq#jak-wstawic-kod-zrodlowy

3) Liczysz nwd w czasie proporcjonalnym do maksimum z tych dwóch liczb (pesymistycznie). Możesz użyć funkcji o nazwie __gcd  znajdującej się w przestrzeni nazw std, która znajduje się w bibliotece algorithm. Ów funkcja działa znacznie szybciej niż twoja implementacja nwd.

Comments

Dzięki wielkie :D z góry przepraszam za błędy, moja pierwsze styczność z tym forum i nie od razu wszystko ogarnąłem, obiecuję poprawę i pozdrawiam :D z tym, że chodzi o NWW, a nie NWD, ale i tak dzięki za pomysł poszukania osobnej funkcji, robiłem na piechotę jak umiałem :D

---

Myślę że rozwiązanie tego zadania nie polega na użyciu funkcji z biblioteki.
Poczytaj na wikipedii o algorytmach liczenia nwd. Istnieją szybkie metody ;)