Zadanie ze Spoj - przedszkolanka

pytanie zadane 12 kwietnia 2016 w C i C++ przez Gravity Nowicjusz (150 p.)

Witam
Chciałem rozwiązać na spoj zadanie. http://pl.spoj.com/problems/PRZEDSZK/ polega ono z tego co mi się wydaje po prostu na znalezieniu najmniejszej wspólnej wielokrotności.
Więc zrobiłem coś takiego

#include <iostream>

using namespace std;

int main()
{
   int a,b,lcm,testamount;
   int multiplea[30], multipleb[30];

   cin>>testamount;
   for (int i=1; i<=testamount; i++)
   {
    cin>>a>>b;
    for (int i=0; i<=29; i++)
    {
        multiplea[i]=a*(i+1);
        multipleb[i]=b*(i+1);
    }
    bool status=false;
    for (int i=0; i<=29; i++)
    {
        if (status) break;
        for (int j=0; j<=29; j++)
        {
            if (multiplea[i]==multipleb[j])
        {
            lcm=multiplea[i]; 
            status = true;
        }
        }
    }
    cout<<lcm<<endl;
   }

    return 0;
}

Zamysł jest taki. Wylicz wielokrotności dwóch liczb a potem je ze sobą porównaj i zapisz najmniejszą liczbę jaką znajdziesz.
Wszystko wychodzi jak powinno ale strona odrzuca to rozwiązanie. Jakieś pomysły o co chodzi?

3 odpowiedzi

odpowiedź 12 kwietnia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Najprostrzy algorytm NWW (a,b) dla każdego zestawu danych

http://www.algorytm.edu.pl/algorytmy-maturalne/nww.html

komentarz 13 kwietnia 2016 przez Gravity Nowicjusz (150 p.)

Niespecjalnie pomaga mi to w zrozumieniu co nie działa w moim pomyśle

odpowiedź 13 kwietnia 2016 przez niezalogowany

Siemka Napisałeś "Wszystko wychodzi jak powinno ale strona odrzuca to rozwiązanie." Zobacz jaki jest na spoj-u komunikat tzn. czy rozwiazanie jest bledne czy przekroczyles limit czasu. Bo w tych zadaniach chodzi glownie o to aby zastosowac konktrenty algorytm i daja takie limity czasowe ze te "proste" sposoby sie nie mieszcza. Jesli problem jest z czasem to musisz zastosowac algorytm NWW (tak jak ktos Tobie juz napisał) Powodzenia