SPOJ upraszczanie ulamków

Question

WItam.

Robię zadanie ze spoja(link poniżej) no i niestety dla mnie mam przekroczony limit czasu, także zwracam się do was z prośbą o pomoc. Nie wiem jak bardziej mogę go uprościć, czy trzeba zrobić to zadanie inną drogą pomimo, że jak dla mnie wyraźnie jest napisane, że trzeba tą, która robiłem. Dziękuję za pomoc.

http://pl.spoj.com/problems/FR_06_13/

#include <iostream>


using namespace std;

int skracanie(int a, int b,int ilosc=1)
{
    if(a==b)
        return ilosc;
    if(a>b)

        return skracanie(a-b,b,++ilosc);
    if(b>a)

        return skracanie(a,b-a,++ilosc);
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        char znak;
        cin>>a>>znak>>b;
        if((a==1)||(b==1))
        {
            if(a>b)
                cout<<a<<endl;
            if(b>a)
                cout<<b<<endl;
            if(a==b)
                cout<<"1"<<endl;

        }

        else
            cout<<skracanie(a,b)<<endl;


    }
    return 0;
}

 

Answer 1

Można wykorzystać algorytm Euklidesa, ale zamiast odejmować można kombinować z dzieleniem.

Answer 2

Dalej w treści jest napisane, że " Niestety algorytm ten, oparty na odejmowaniu ma jedną dużą wadę. Czasami liczba odejmowań, jakie trzeba wykonać, jest tak duża, że lepiej pozostawić ułamek w spokoju," I jest to prawda, bo nieistotne, że sprawdziłeś czy a lub b nie są równe 1, skoro a może być równe 10^9, a b równe 2 i twój program wykona ~ miliard operacji, kiedy powinniśmy celować w co najwyżej dziesiątki milionów operacji. Zadanie polega wykorzystaniu operacji dzielenia i dzielenia z resztą ( '%' w c++ ), i polega na dodaniu jednej linijki kodu do algorytmu euklidesa (który z resztą też można zapisać w jednej linijce kodu)