Lampki
Limit pamięci: 64 MB
Mały Jaś dostał na święta nietypowy prezent.
Po odpakowaniu kolorowego kartonu jego oczom ukazał się napis
"Nieskończony łańcuch lampek choinkowych".
Zainteresowany chłopiec od razu rozłożył nową zabawkę na podłodze.
Łańcuch Jasia ma formę kabla posiadającego początek,
ale nieposiadającego końca.
Do kabla są podłączone lampki ponumerowane (zgodnie z kolejnością na
kablu) kolejnymi liczbami naturalnymi, poczynając od .
Kabel podłączony jest do panelu sterowania.
Na panelu znajduje się pewna liczba przycisków, każdy w innym
kolorze i przy każdym znajduje się inna dodatnia liczba
naturalna.
Liczby umieszczone przy różnych przyciskach są parami względnie
pierwsze.
W momencie rozpakowania prezentu żadna lampka się nie świeciła.
Jaś, nie myśląc wiele, przycisnął po kolei wszystkie przyciski
na panelu sterującym, od pierwszego aż do ostatniego.
Ze zdumieniem zaobserwował, że naciśnięcie -tego przycisku
powoduje zapalenie się wszystkich lampek o numerach podzielnych
przez liczbę znajdującą się przy tym przycisku.
Co więcej, wszystkie te lampki zaczynają świecić kolorem ,
takim jak kolor przycisku.
W szczególności, wszystkie lampki o numerach podzielnych przez
, które były już uprzednio zapalone, zmieniają swój kolor
na kolor .
Teraz Jaś patrzy urzeczony na nieskończony wielobarwny łańcuch
i zastanawia się, jaka część lampek pali się poszczególnymi
kolorami.
Oznaczmy przez liczbę lampek palących się na kolor
, spośród lampek o numerach .
Formalnie, ułamek lampek, które palą się kolorem , to:
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opisy przycisków na panelu sterowania,
-
dla każdego koloru obliczy ułamek , mówiący
jaka część lampek pali się kolorem ,
-
wypisze wyniki na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę przycisków znajdujących się na panelu
sterowania.
Kolejne wierszy zawiera po jednej liczbie całkowitej
(),
oznaczającej, że przyciśnięcie -tego przycisku powoduje zapalenie się na kolor
lampek o numerach podzielnych przez .
Liczby są podane w kolejności naciskania przycisków przez
Jasia.
Liczby są parami względnie pierwsze i różne.
Wyjście
Twój program powinien wypisać na wyjście dokładnie wierszy.
W -tym z nich powinien się znaleźć ułamek ,
mówiący jaka część lampek pali się kolorem ,
zapisany w formie nieskracalnego ułamka ,
gdzie jest całkowite, całkowite dodatnie oraz
i są względnie pierwsze.
Jeśli , to ułamek ten powinien być wypisany jako .
Przykład
Dla danych wejściowych:
3
2
3
5
poprawną odpowiedzią jest:
4/15
4/15
1/5
Autor zadania: Michał Pilipczuk.