W dniu 2011-05-24 20:28, t...@g...SKASUJ-TO.pl pisze:
> witam,
>
> jak sprawdzic czy dla integerow a,b,c,d zachodzi
>
> a*b == c*d

Jak a i b są 32 bitowe, to piszemy ((long long)a)*b i porównujemy.
Jak 64, a maszyna x64, to VS i gcc mają jakieś typy 128bitowe
i podobnie. W strasznym języku ja J mamy duże liczby;)


> Chodzi raczej o to, czy ktos zna zestaw warunkow
> typu mnozenie, dodawanie
> modulo,


Ok, a jak podam rozwiązanie, to co dostane?

Masz porównać ab == cd

porównaj ab == cd (mod p_i)

dla kilku liczb pierwszych, w miarę dużych i takich,
by p^2 mieściło się w zakresie.
Z górką wystarczy 5 takich liczb*)

Jeśli m==n (mod p_i), dla i=1..k
to m==n jeżeli tylko m i n < p_1*p_2*...*p_k

Nazywa się toto Chińskie twierdzenie o resztach.
p_i nie muszą być nawet pierwsze, wystarczy, że są względnie pierwsze.


*)P< sqrt(MAXINT), ale możemy dobrać niewiele mniejsze.
p_1*..*p^5 wyniesie ponad MAXINT^2




Mnożenia a*b wykonujesz mod p: ((a%p)*(b%p))%p
więc nigdy nie wyskoczysz poza zakres.

Wydaje się, że więcej pracy niż przy ((long long)a)*b==((long long)c)*d,
ale za to ładnie skaluje się, liniowo ze względu na ilość czynników
w iloczynie (czego nie można powiedzieć o mnożeniu dużych liczb).

No i jest niezależne od języka, maszynerii i tego, czym tak naprawdę
są te inty.


Ktoś podesłał pomysł rozkładu na czynniki pierwsze. Można pociągnąć
ten pomysł. Policzymy NWD (najwiekszy wspolny dzielnik)
dla wszytkich możliwytch par i będziemy skracać.

x=NWD(a,c);
a=a/x; c=c/x;

i podobnie dla par a:d, b:c, b:d (najpierw skracamy, pozniej
liczymy kolejne NWD)

Po wszystkich skróceniach, jeśli iloczyny były równe, otrzymamy
cztery jedynki.

Algorytm liczący NWD znajdziesz bez problemu, jest prosty i szybki,
a imię jego Euklides.


Chyba trudniej byłoby ze stwierdzeniem, która liczba jest większa.


pozdrawiam
bartekltg