题目描述

After sailing the Seven Seas and raiding many ships, Cap'n Red and his crew of fellow pirates are finally ready to divide their loot. According to ancient traditions, the crew stands in a circle ordered by a strict pirate hierarchy. Cap'n Red starts by taking a fraction $f$ of the loot and passing the remainder on to the next pirate. That pirate takes the same fraction $f$ of the loot left over by the previous pirate and passes the remainder on to the following pirate. Each pirate behaves in the same way, taking a fraction $f$ of what is left and passing on the rest. The last pirate in the hierarchy passes the remainder on to Cap'n Red, who starts another round of this "fair" division, and so on, indefinitely.

Fortunately, pirates in the 21st century can use a computer to avoid this lengthy process and constant nitpicking when the fraction $f$ does not exactly divide the loot at some step. You have been captured by the pirates and asked to come up with a suitable fraction $f$. As an incentive, Cap'n Red has promised to leave you alive if you succeed.

The fraction $f$ needs to be a rational number strictly between $0$ and $1$. It is not necessary that $f$ exactly divides the loot remaining at any step of the round-robin process described above. However, the total loot that would be assigned to each pirate by carrying out this process infinitely needs to be an integer.

输入格式

The input contains one line with two integers $n$ and $m$, where $n$ ($6 \leq n \leq 10^6$) is the number of pirates including Cap'n Red and $m$ ($1 \leq m \leq 10^{18}$) is the total value of their loot.

输出格式

Output one line with two positive integers $p$ and $q$, where $f = \frac{p}{q}$ as specified above. If there are multiple suitable fractions, choose one with the smallest $q$. Among multiple suitable fractions with the same smallest $q$ choose the one with the smallest $p$. If there is no suitable fraction, output $\texttt{impossible}$ instead and hope for mercy.

题目大意

题目描述

$n$ 个人按如下的方式分 $m$ 块钱：先指定一个分数 $f$，$n$ 个人围成一圈，第一个人先拿走总钱数的 $f$，把剩下的钱给第二个人，然后第二个人拿走剩余钱数的 $f$，把剩下的钱交给第三个人...每一个人都从剩余的钱中拿走剩余钱数的 $f$，然后把钱交给下一个人。这种操作可以无限进行下去。

现在给定 $n,m$，你需要构造 $f=\dfrac{p}{q}$，使得 $0<f<1$，并且在分钱无限进行下去之后，最终每个人拿到的钱都是整数。如果有多解，你构造的解需要在 $q$ 尽可能小的情况下 $p$ 尽可能小。如果无解，输出 impossible。

$6\le n\le 10^6$，$1\le m\le 10^{18}$。

输入格式

仅一行两个整数 $n,m$，含义如题目所述。

输出格式

如果有解，输出一行两个整数 $p,q$，分别是你构造的分数 $f$ 的分子和分母。

如果无解，输出 impossible。

8 51000

1 2

6 91000

2 3

10 1000000000000000000

impossible