ARC#004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

(N(N+1)/2-M)/N = X/Y

を変形して、

N = 2(X/Y+M/N)-1

Nが整数であることと、0＜M/N≦1であることから、Nはfloor(2*X/Y)とfloor(2*X/Y)+1。それぞれについてMを求めて、正しいかチェック。

from fractions import Fraction

X = Fraction(raw_input())

f = False
for i in range(2):
    N = int(2*X)+i
    M = N*(N+1)/2-X*N
    if M==int(M) and 1<=M<=N:
        print N,M
        f = True
if not f:
    print "Impossible"