OI题库

【题目描述】

Great Dodgers公司最近开发了一种全新的游戏机。

游戏机的玩法是：你向机器内放一枚硬币，拉动手柄。然后它会随机选一个整数。如果选中的整数是0你就赢了头奖。否则游戏机会用幸运数字p1,p2,...,pn分别去除选中的数。如果这n个余数中至少有一个是0，你也赢了。

Great Dodgers公司希望计算他们游戏机上玩家的获胜概率。他们尝试这么做，但失败了。因此Great Dodgers雇佣了你来写一个程序计算上面所说的概率。

一名数学家提示你，所求的概率可以用如下极限表示：

lim_k→∞(S_k/2k+1).

其中Sk是在-k到k之间且能被至少一个幸运数字整除的整数数量。

【输入格式】

输入文件的第一行有一个整数n（1<=n<=16），即幸运数字的数量。

接下来是n个幸运数字（1<=pi<=10^9）.

【输出格式】

显然所求的概率是一个有理数。用最简分数的形式输出它。

输出文件的第一行是获胜概率的分子，第二行是分母。分子和分母都不能有前导零。记住必须输出最简形式。

【样例输入】

2
4 6

【样例输出】

1
3

【来源】

Northeastern Europe(NEERC) 2004,Northern Subregion - Problem J.Jackpot

POJ 2103 Jackpot