Przekroczony limit czasu - optymalizacja kodu

Przekraczam ilość czasu na SPOJU. http://pl.spoj.com/problems/PP0501A/ Co tu można poprawić?

public static void main(String[] args) {
        
         Scanner skaner = new Scanner(System.in);
         int liczbaTestow = skaner.nextInt();
         
         for(int i=0;i<liczbaTestow;i++) {
             int a,b;
             a = skaner.nextInt();
             b = skaner.nextInt();
             int m = 0;
             if(a>b){
                 m = b;
                 if(m<0){
                     m=-m;
                 }
             }
             else if(b>a){
                 m = a;
                 if(m<0){
                     m=-m;
                 }
             }
             for(int j=m;j>0;j--){
                 int c = a%j;
                 int d = b%j;
                 if(c==0 && d==0){
                     System.out.println(j);
                     break;
                 }    
             }
         }
         
    }

użyj algorytmu Euklidesa

SPOJ to przyjął, ale jestem ciekawy czy to dalej wygląda słabo. ?

Scanner skaner = new Scanner(System.in);
        int a,b,iloscTestow;
        iloscTestow = skaner.nextInt();
        int m;
        int t;
        
        for(int i=0;i<iloscTestow;i++){
            a = skaner.nextInt();
            b = skaner.nextInt();
            while(a!=0 && b!=0){
                if(a>b){
                a = a - b;
                }
                else{
                b = b - a;
                }
            }
            if(a==0){
                System.out.println(b);
            }
            else if(b==0){
                System.out.println(a);
            }
        }

Poprzedni program musiał się wykonywać powyżej 1 sekundy skoro SPOJ go nie przyjął. Ten miał 0,14s. Aż taka różnica?

Aż taka różnica?

Nooooo.

jestem ciekawy czy to dalej wygląda słabo. ?

Mogłeś użyć dzielenia modulo zamiast odejmowania.

Dzielenie modulo chyba nic nie zmienia? W czym tkwi ta duża różnica w wykonywaniu się programów, w czasie?

Pomyśl jak będzie się wykonywać każda wersja programu (pierwsza naiwna, druga z odejmowaniem, trzecia z dzieleniem modulo) dla dwóch wielkich liczb (rzędu miliard), które nie mają wspólnego dzielnika. Wystarczy rozpisać na kartce pierwsze 10 działań dla każdej wersji to zrozumiesz.

Porównaj jeszcze na kartce (bardzo wielu kartkach) przebieg algorytmów z odejmowaniem i dzieleniem modulo dla liczb 2 000 000 000 i 1.

@bogdans, jestem już przy 100000.

SPOJ http://pl.spoj.com/problems/FCTRL3/ Limit czasu przekroczony. Jakaś podpowiedź?

public static void main(String[] args) {
        
        Scanner skaner = new Scanner(System.in);
        int liczbaTestow = skaner.nextInt();
        
       for(int i=0;i<liczbaTestow;i++) {
            int liczba1 = skaner.nextInt();
            int pomocnik = liczba1;
            for(int j=1;j<pomocnik;j++){
                liczba1 *= j;
            }
                int a = liczba1/10;
                int b = liczba1%10;
                System.out.println(a+" "+b);
            
        }
    }

Źle zrozumiałem na początku polecenie, myślałem, że chodzi o LICZBĘ dziesiątek.. Nie zauważam nic regularnego poza dwoma zerami od silni>=10. Mogę zastosować ifa, ale.. czy tu chodzi o rządek ifów?

jabluszko napisał(a):

Nie zauważam nic regularnego poza dwoma zerami od silni>=10.

To już chyba wystarczające spostrzeżenie.

Co zrobisz dla liczb 1<=x<10 to już raczej bez znaczenia. Jak będzie wprowadzona liczba z tego zakresu to możesz to obliczać, możesz też zahardkodować wyniki dla tych 10 przykładów w jakiejś mapie.

A tak btw. to raczej mało które zadanie na SPOJu przejdzie jak w każdym będziesz robił bruteforca.