Tylko dla orlow - niebanalny problem

[Myszaq]

Witam wszystkich,

Spotkalem sie z nietypowym problemem:


Mam dowolny ulamek - A / B
gdzie:
- A jest rozne od B
- A nie jest wielokrotnoscia B

Chcialbym znalesc odpwowiedz na pytanie:
ILE RAZY nalezy dodac do liczby A znana z gory liczbe S ( S > A) aby ulamek przybral forme liczby calkowitej
czyli A+(x*S) = B albo A+(x*S) wielokrotnosc B. Szukam oczywiscie najmniejszego mozliwego x.


Inaczej mozna zapisac to w nastepujacy sposob:
(A + x*S) / B
Majac dane A, B, S gdzie ( S > A ) szukam najmniejszego x tak aby (A + x*S) = B lub (A + x*S) bylo wielokrotnoscia B.


Przyklad:

A = 3 B = 8 S = 5

Otrzymujemy : (3 + x*5) / 8
Oczywiscie rozwiazaniem jest x = 1, czyli do 3 wystarczy raz dodac liczbe 5, aby otrzymac ulamek 8 / 8 co jest liczba calkowitka.


Serdecznie prosze o jakies sugerstie lub wskazowki,
Z gory serdecznie dziekuje.

[LecHu :)]

Zbadaj mozliwe reszty z dzielenia liczby S przez B.

[juzef]

Algorytm Euklidesa. Jeśli nie wiesz jak, poszukaj w książce Wprowadzenie do algorytmów Cormena, rozdział algorytmy teorioliczbowe, rozwiązywanie modularnych równań liniowych.