SPOJ - nwd błąd odpowiedzi

Question

Hej !

Próbuję rozwiązać zadanie NWD ze spoja. Program po zrobieniu testów, zarówno podanych jako przykłady na stronie spoja jak i innych, pokazuje mi dobre wyniki, w kompilatorze. Jedank spoj nie zatwierdza zadania (błąd odpowiedzi). Próbował znaleźć błąd jednak brak mi już pomysłów. Chętnie przyjmę wszelkie sugestię

int nwd(int a, int b)
{
    int p;
    p=a%b;
    if (p!=0)
    {
        for(int i=1;i<=p;i++)
        {
            p=a%b;
            a=b;
            if(p!=0) b=p;
        }

        return b;
    }
    else return b;
}

    int t,a,b;
    cin >> t;
    for(int i=1;i<=t;i++)
    {
            cin >>a>>b;
            if ((a>=0) && (b<=1000000))
            {
                cout<< nwd(a,b) << endl;
            }
    }

 

Answer 1

To jest bardzo niestandardowa implementacja liczenia nwd. Z tego co zauważyłem to masz błędy chociażby dla tego testu:

2

21 34

10 0

Wydaje mi się, że jak już to w linii 7 powinno być i <= c_p, gdzie c_p to kopia zmiennej p. Ale nawet po tej zmianie ten algorytm nie będzie raczej działał dla większych liczb.  Poza tym ten algorytm jest za wolny i nie zmieści się w limicie czasu

Comments

ok dziękuje.