Memory limit: 64 MB
Little Johny has received a most unusual Christmas present. The sign on the freshly unwrapped box read "Infinite chain of fairy lights". Amused, the boy laid out his new toy on the floor.
Johny's chain is a cable with but one end: it begins at some point, but does not end anywhere. Attached to the cable are fairy lights, numbered (in order of attachment) with successive natural numbers, starting with . The cable itself is plugged to a control panel. There is a number of buttons on the panel, each uniquely colored and each inscribed with unique positive integer. The numbers inscribed to the buttons are pairwise relatively prime.
Upon unwrapping, no light was turned on. Thinking little at the time, Johny pressed all the buttons one by one, from first to last. To his increasing amusement he noticed that pressing the button turns on exactly the lights which numbers are multiples of , the number inscribed on the button. Moreover, they are burning in the color , the one of the button. In particular, all the lights whose numbers are multiples of that were previously lit, change their color to .
Johny gazes infatuated at the infinite multicolour chain and wonders what fraction of the lights burns with each particular colour. Let denote the number of lights burning with the colour among the lights with numbers . Formally, the fraction of the lights burning with colour is defined as:
Write a programme that:
- reads the descriptions of the buttons on the control panel from the standard input,
- for each colour calculates the fraction , denoting the fraction of lights burning with the colour ,
- writes out the result to the standard output.
The first line of the standard input contains a single integer (), denoting the number of buttons on the control panel. Each of the following lines contains a single integer (), meaning that pressing the button makes the lights numbered with multiples of burn with the colour . The numbers are given precisely in the order Johny had pressed them. The numbers are pairwise relatively prime (and thus different).
Your programme should write out exactly lines to the standard output. The line should contain the fraction of the lights burning with colour , written as a fraction , where jest is an integer, is a positive integer and and are relatively prime. If , the fraction should be written as
For the input data:
3 2 3 5
the correct result is:
4/15 4/15 1/5
Task author: Michal Pilipczuk.<Submit a solution> [0/100]