C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi ) Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

太郎君は 1 から N までの正整数の平均値を求めようと思い、1 から N までの合計値を N で割ることにしました。
しかし、1 から N までの正整数を合計するときに、ある正整数 M(M は N 以下の正整数)だけ足し忘れてしまい、間違った平均値を算出してしまいました。
さらに、太郎君は正整数 N の値も忘れてしまいました。

今、間違った平均値だけがわかっています。元の数 N と M の組み合わせとして考えられるものを全て答えてください。

入力

入力は以下の形式で標準入力から与えられる。 
X/Y
  • 入力は 1 行のみからなり、間違った平均値が分数の形で与えられる。
  • 分数は整数 X(1≦X≦10^{18})、/、整数 Y(1≦Y≦10^9) の順で与えられ、間違った平均値が X/Y であることを表す（0 < X/Y≦10^9）。
  • ただし、入力は既約分数とは限らない。

出力

N と M(1≦M≦N) の間に空白を区切りとして入れて、N と M の組み合わせとして考えられるものを全て N の値が小さい順に標準出力に出力せよ。
ただし、考えられる答えが複数ある場合は 1 行に N と M を 1 組ずつ出力し、考えられる答えが無い場合は Impossible と答えること。
なお、最後には改行を出力せよ。

入力例 1

4/3

出力例 1

3 2
  • N=3、M=2 の時、間違った平均値は (1+3)/3 = 4/3 となり、入力を満たします。
  • したがって、この組み合わせが答えとなります。

入力例 2

4/6

出力例 2

Impossible
  • 入力値を満たすような解は存在しません。

入力例 3

49995/10

出力例 3

10000 10000
  • N=10,000、M=10,000 の時、間違った平均値は (1+2+...+9999)/10000 = 4995000/10000 = 49995/10 となり、入力を満たします。

入力例 4

1/400

出力例 4

Impossible

Source Name

ARC 004