Ile różnych liczb zmiennoprzecinkowych

Witam!

Mam problem z pewnym zadaniem. Zadanie polega na wypisaniu ile różnych liczb można uzyskać z l-bitowego licznika i m-bitowego mianownika (mianownik musi być rozny od 0, liczby bez znaku)

Dla l = 2, m = 2 poprawny wynik to 8 (0/1, 1/1, 1/2, 1/3, 2/1, 2/3, 3/1, 3/2).

0/1 = 0/2 = 0/3 (wybralem tylko jedna pierwszą wersje)
1/1 = 2/2 = 3/3 (jak wyzej..)

Zna ktoś jakiś algorytm na obliczenie wyniku? Powiedzmy ze l, m <= 32.
Da sie to obliczyc ze złożonością O(1)?

Nic lepszego niż nwd nie widzę.
Aczkolwiek należy pokombinować z:
Maksymalny licznik: L=2²⁴
Maksymalny mianownik: M=2³²-1
Więc ułamek a/b eliminuje: min(floor(a/L)-1,floor(b/M)-1) innych ułamków.

_13th_Dragon napisał(a):

Nic lepszego niż nwd nie widzę.

Możesz pokazać jak to zrobić tym sposobem?

Dla pary (l,m) obliczasz nwd(l,m). Jeżeli obliczony nwd jest większy niż 1, to parę (l,m) pomijasz.

xxxmateusz00xxx napisał(a):

Da sie to obliczyc ze złożonością O(1)?
Oczywiście, że się da. Wystarczy stabilizować wszystkie możliwe wyniki dla sensownych danych, których nie jest bardzo dużo (ty masz ograniczenie do 32x32).

Warto też poczytać o: http://pl.wikipedia.org/wiki/Funkcja_%CF%86