QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100

#5103. 公平分配

Statistics

在航行七海并劫掠了许多船只后,红船长(Cap’n Red)和他的海盗船员们终于准备好瓜分战利品了。根据古老的传统,船员们按照严格的海盗等级制度围成一个圆圈。红船长首先拿走战利品的 $f$ 分之一,并将剩余部分传给下一位海盗。该海盗从前一位海盗留下的战利品中拿走同样的 $f$ 分之一,并将剩余部分传给下一位海盗。每位海盗都以同样的方式行事,拿走剩余部分的 $f$ 分之一并将余下的部分传下去。等级制度中的最后一位海盗将剩余部分传回给红船长,红船长开始新一轮的这种“公平”分配,如此循环往复,永无止境。

幸运的是,21 世纪的海盗可以使用计算机来避免这种漫长的过程,以及当 $f$ 在某一步不能整除战利品时产生的持续争执。你被海盗们抓住了,并被要求给出一个合适的比例 $f$。作为激励,红船长承诺如果你成功了,就饶你不死。

比例 $f$ 需要是一个严格介于 0 和 1 之间的有理数。在上述循环分配过程的每一步中,$f$ 并不要求必须能整除剩余的战利品。然而,通过无限次执行此过程,分配给每位海盗的战利品总额必须是一个整数。

输入格式

输入包含一行,包含两个整数 $n$ 和 $m$,其中 $n$ ($6 \le n \le 10^6$) 是包括红船长在内的海盗人数,$m$ ($1 \le m \le 10^{18}$) 是战利品的总价值。

输出格式

输出一行,包含两个正整数 $p$ 和 $q$,其中 $f = \frac{p}{q}$,如上所述。如果有多个合适的比例,请选择 $q$ 最小的一个。在具有相同最小 $q$ 的多个合适比例中,选择 $p$ 最小的一个。如果没有合适的比例,则输出 impossible 并祈求宽恕。

样例

样例输入 1

8 51000

样例输出 1

1 2

样例输入 2

6 91000

样例输出 2

2 3

样例输入 3

10 1000000000000000000

样例输出 3

impossible

Figure 1. 红船长(Cap’n Red)

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.