時間制限:20000ミリ秒
メモリ制限:64000KB
1ケースあたりの時間制限:2000ミリ秒
問題
グレートドジャーズ社はこの度新たなゲームを開発した。
このゲームにコインを入れてハンドルを引くと、数が1つ選ばれる。もし選ばれた数が0ならジャックポットを獲得することができる。0でない場合このゲームはこの数をラッキーナンバーの p1, p2, ..., pn で割ろうとしてみる。そして、そのうち1つでも、余りが0になるようなラッキーナンバーがあればあなたの勝ちである。
グレートドジャーズ社はこのゲームに勝てる確率がどれぐらいになるかを計算したくて、実際に挑戦したみたものの失敗した。そこでグレートドジャーズ社はこの計算をするプログラムを書かせるためにあなたを雇った。
残念なことに、全ての数が等しい確率で選ばれると仮定することはできないが、ある一人の数学者があなたにこんなことを言った。「求めるべき数は次のような極限によって近似できる」
lim[k→∞] (S[k] / 2k+1)
ここで S[k] とは、 -k から k までの整数のうち、ラッキーナンバーの最低どれか1つで割り切れるような数の個数である。
入力
入力の最初には n 、ラッキーナンバーの個数が書かれている(1 ≦ n ≦ 16)、そしてそれに n 個のラッキーナンバー pi (1 ≦ pi ≦ 10^9) が続く。
出力
結果が分数の形で表されるのは明らかなので、その分数を既約分数の形で出力せよ。
一行目には勝率を表す分数の分子、二行目には分母をそれぞれ出力せよ。分子、分母はそれぞれ先頭に余計な0を含んではいけない。分数は既約分数の形でなければならないことに注意せよ。
入力の例
2
4 6
出力の例
1
3
出典
Northeastern Europe 2004, Northern Subregion