Am primit problema asta la oli si nimeni n-a rezolvat-o in concurs si probabil n-o sa fie solutii oficiale. Imi poate spune cineva cum se rezolva
?
PROBLEMA 2 – Fracţie
Algorel a învăţat la matematică despre mulţimea numerelor naturale şi mulţimea numerelor raţionale. El poate să numere foarte uşor de la 1 la n în mulţimea numerelor naturale şi ar dori să numere la fel de simplu şi în mulţimea numerelor raţionale. Pentru un număr natural dat n, el scrie toate fracţiile ireductibile subunitare cu numitorul cel mult egal cu n în ordine crescătoare (şirul începe cu 0=0/1 şi se termină cu 1=1/1).
De exemplu, pentru n=5 obţine şirul de fracţii: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.
Ajutaţi-l pe Algorel şi scrieţi un program care pentru un număr n şi o fracţie a/b date returnează fracţia scrisă după aceasta în şirul ordonat crescător al fracţiilor ireductibile cu numitorul mai mic sau egal cu n.
Date de intrare
Fişierul de intrare fractie.in conţine pe prima linie, separate prin câte un spaţiu, numerele naturale n, a şi b, n reprezentând numitorul maxim al fracţiilor din şir, iar a şi b numărătorul şi numitorul fracţiei date.
Date de ieşire
Fişierul de ieşire fractie.out va conţine pe unica sa linie două numere separate printr-un spaţiu, reprezentând prima fracţie mai mare decât a/b din şirul ordonat crescător al fracţiilor ireductibile cu numitorul mai mic sau egal decât n.
Restricţii şi precizări
1 ≤ a < b ≤ n ≤ 1 000 000 000
Exemplu
fractie.in fractie.out
5 2 3 3 4
Explicaţie
pentru n=5 se obţine şirul de fracţii: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1, iar răspunsul este 3/4
Timp maxim de execuţie/test : 1 secundă