Znajdz dwie liczby, ktorych NWD=x

Dla specjalistów Programowanie
#1

Przygotowywuje sie do olimpiady informatycznej poprzez robienie zadan z poprzednich lat i dorwalem takie zadanie: http://www.oi.edu.pl/html/zadania/oi14/zapzad.pdf.

Trzeba znalezc ilosc takich par liczb x oraz y, ze NWD(x,y)=d. Mamy podany zakres jaki moga osiagnac liczby x oraz y i dana jest liczba d. Moj problem polega na tym, ze w najgorszym wypadku zwyczajne sprawdzanie po kolei kombinacji x i y moze wywolac fukcje NWD nawet 2 500 000 000 razy! To zdecydowanie za duzo, wiec poszukuje efektywnego algorytmu mogacego rozwiazac ten problem.

Mam juz pewnien pomysl jak zmniejszyc zlozonosc programu, ale wole poradzic sie teższych glow.

Chodzi mi tylko o ogolny zarys algorytmu, ktory znajdzie te dwie liczby, choc moze byc rowniez listing w C/C++, Pascalu lub najlepiej w JAVA.

To nie jest prosba o rozwiazanie zadania konkursowego, tylko o pomoc w przygotowaniu sie do niego.

#2

Moge rzucic kilka hintow, nie chce mi sie calego rozwiazywac.

x = a*d

y = b*d

Zeby NWD(x,y) = d to NWD(a,b) = 1, z czego wynika ze a i b nie moga miec w swoich rozkladach _zadnych_ wspolnych czynnikow. Szukana przez ciebie ilosc kombinacji to w rzeczywistosci ilosc takich par a i b, by a*d i b*d nie przekroczylo danego zakresu. (wygeneruj liczby pierwsze z od 1 do zakresu podanego w zadaniu, podzielonego przez d - a nastepnie generuj z nich a i b)

#3

To ze nie ma potrzeby sprawdzac wszystkich kombinacji tylko uzywac liczb a*d domyslilem sie wczoraj, ale niestety nie moge sie zgodzic z Toba ze powinieniem wykorzystac liczby pierwsze… Prosty przyklad NWD(40,44)=4

40=10*4=10*d

44=11*4=11*d

11 jest liczba pierwsza ale 10 juz nie jest bo jest zlozoną liczbą, wiec gdybym postepował wg takiego algorytmu pominał bym te parę liczb i na pewno duzo wiecej takich dwójek liczb, wiec pomysl z liczbami pierwszymi odpada.

Mozliwe ze korzystanie z liczb a*d tak skroci czas wykonania programy ze inne zabiegi nie bdą potrzebne.

#4

Tu jest haczyk:

(wygeneruj liczby pierwsze z od 1 do zakresu podanego w zadaniu, podzielonego przez d - a nastepnie generuj z nich a i b)

10 to w rozkladzie na czynniki 2*5 - 2 i 5 to liczby pierwsze. Moj pomysl polega na tym, ze generujesz liczby pierwsze do zakresu podanego w zadaniu, pozniej z nich generujesz a i b tak, by nie przekraczaly zakresu. (a wlasciwie zakresu podzielonego przez d).

===========================

Nie używaj zastrzeżonych kolorów.

Zacznij stosować się do punktu 2.14

Monczkin

#5

troszke chyba za duzo kombinowania z tymi liczbami pierwszymi, bo to jednak zwiekszy bardziej zlozonosc programu niz bez tych liczb… narazie sprobuje to rozpykać bez liczb pierwszych po prostu uzywajac kolejnych wielkokrotnosci liczby d

wielkie dzieki :smiley:

Złączono Posta : 18.10.2007 (Czw) 17:57

znlazlem, wydaje mi sie, najoptymalniejszy algorytm:

a) korzystam w nim tak jak we wczesniejszych postach pisano z wielokrotnosci liczby d

b) ‘dzielę’ tablice utworzana z zakresow a oraz b na ‘kwadratowa’ tablice i pozostalosc = po prostu poczatkowo korzystam tylko z liczb spelniajacych nizszy zakres;

-teraz aby to mialo jakis sens to wyszukuje tak liczby aby kolejnosc (y,x) nie pojawila sie, tylko korzystam wylacznie z (x,y) - przynajmniej poczatkowo; tylok ze takie uproszczenie pomija kombinacje (y,x) wiec wynik dla tej kwadratowej tabeli musi wygladac tak: wynik1=wynik_odtrzymany_kwadracie * 2 - 1

-w pozostalej czesci tablicy postepuje juz normalnie czyli sprawdzam po kolei wszystie mozliwe kombinacje (dalej korzystam z wieloktronosc d, jednak juz nie bawie się w dzielenie ‘tablicy’)

c) teraz pozostaje juz tylko dodanie obydwu wynikow i mamy calkowita liczbe mozliwych kombinacji

tutaj moj kod w javie:

//Rafał C***t 2007

import java.io.*;

import java.util.*;


public class zapytania{

  static int nwd(int x, int y){

    int c;

     while (y != 0) {

                c = x % y;

                x = y;

                y = c;}

    return x;

  }


  static int min(int poczatek, int skok){

    while(poczatek%skok!=0)

      poczatek++;

    return poczatek;

  }



  public static void main(String[] args){

    BufferedReader wejscie = new BufferedReader( new InputStreamReader(System.in) );

    int n; //liczba zapytan

    int a, b, d, wynik, wynik_temp, min;

    int[] wynik_koncowy;


    try{

      n = Integer.parseInt( wejscie.readLine() );

      StringTokenizer st;

      wynik_koncowy = new int[n];


      for(int i=0; i
        st = new StringTokenizer(wejscie.readLine(), " ");

        a = Integer.parseInt( st.nextToken() );

        b = Integer.parseInt( st.nextToken() );

        d = Integer.parseInt( st.nextToken() );

        wynik=0;wynik_temp=0;


        if(a>b){

          for(int x=d; x<=b; x+=d) //zacznij od nwd i zwiekszaj je o nwd, nie sprawdza do konca aby oszczedzic

            for(int y=x; y<=b; y+=d) //y=x skrocenie tyczas. o polowe szukanie par

              if(nwd(x,y)==d) wynik++; //jesli nwd(x,y) jest rowne d to zwieksz liczbe par

          if(wynik>0) wynik_temp=2*wynik - 1; //prawidlowy wynik dla przedzialu (wynika ze skrocenia: patrz 2 linijki wyzej)


          min = min(b+1,d); //znalezienie nowej dolnej granicy przedzialu pominietego wyzej

          wynik=0; //inicjacja na nowo zmiennej wynik

          for(int x=min; x<=a; x+=d) //rozpoczecie szukania od nowgo przedzialu

            for(int y=d; y<=b; y+=d) //a tutaj szukanie za porzadkiem

             if(nwd(x,y)==d) wynik++;

          wynik_koncowy[i]=wynik+wynik_temp; //suma z obydwu przedzialow

        }

        else if(a
          for(int x=d; x<=a; x+=d)

            for(int y=x; y<=a; y+=d)

              if(nwd(x,y)==d) wynik++;

          if(wynik>0) wynik_temp=2*wynik - 1;


          min = min(a+1,d);

          wynik=0;

          for(int x=d; x<=a; x+=d)

            for(int y=min; y<=b; y+=d)

            if(nwd(x,y)==d) wynik++;


          wynik_koncowy[i]=wynik+wynik_temp;

         }

         else{ // a==b

          for(int x=d; x<=a; x+=d)

            for(int y=x; y<=a; y+=d)

              if(nwd(x,y)==d) wynik++;

          if(wynik>0) wynik_temp=2*wynik - 1;


          wynik_koncowy[i]=wynik_temp;

         }

      }


      for(int i=0;i
        System.out.println(wynik_koncowy[i]);

    }

    catch(IOException w){};

  }

}

//Rafał C***t 2007[/code]