#P2645. Boastin' Red Socks

    ID: 1645 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>搜索枚举模拟组合数学Waterloo local 1999.06.19

Boastin' Red Socks

题目描述

你有一个抽屉,里面装满了两种颜色的袜子:红色和黑色。你知道抽屉里至少有 2 只袜子,并且不超过 50000 只。然而,你不知道袜子具体有多少只,也不知道红色袜子有多少只,黑色袜子有多少只。(是你妈妈负责洗衣服的!)

不过,你注意到,每天早上当你把手伸进抽屉里挑选两只袜子来穿的时候(在漆黑的环境中,所以你无法区分红色和黑色),你挑出两只红色袜子的概率恰好是p/qp/q,其中q>0q > 00pq0 \leq p \leq q

基于这一信息,你能确定抽屉里每种颜色的袜子各有多少只吗?可能存在多个解——如果是这样的话,选择袜子总数最少的那个解。

输入

输入由多个问题组成,每个问题占一行。每个问题由两个用单个空格分隔的整数ppqq组成。请注意,ppqq都可以用无符号长整型来表示。

输入以包含两个零的一行作为结束标志。

输出

对于每个问题,输出一行,由抽屉中红色袜子的数量和黑色袜子的数量组成,两者之间用一个空格分隔。如果该问题没有解,则输出“impossible”。

输入数据 1

1 2
6 8
12 2499550020
56 789
0 0

输出数据 1

3 1
7 1
4 49992
impossible

题目来源

Waterloo local 1999.06.19