QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 2048 MB 満点: 25

#2731. 笛卡尔征服

統計

很久以前,在 Cartesia 大地上,统治着矩形帝国。帝国幅员辽阔、繁荣昌盛,通过频繁的征服成功地扩张了领土。这个古老文明的公民遵循着许多奇特的习俗。遗憾的是,这些习俗的意义如今已湮没在神秘之中。

矩形帝国采用矩形行政区划系统。这些行政区经过精心管理,以满足三个特殊标准:

  1. 帝国的领土被划分为若干行政区,使得帝国控制下的每一块土地都恰好属于一个行政区。
  2. 在地图上观察时,行政区的边界必须是矩形,且矩形长边的长度必须是短边长度的两倍。
  3. 当以 $\Xi$ 为单位测量时,行政区的边长必须是整数(注意 $\Xi$ 是矩形帝国的主要长度单位)。

帝国初建时,仅由一个行政区组成。此后,帝国通过征服邻近地区获得了额外的行政区。每当帝国获得一块新土地的控制权时,他们总是利用这块土地建立一个单一的新行政区。这意味着帝国在征服土地时,总是会考虑到土地的几何特性。你可以假设这些征服行动不会同时发生。

增加新行政区是帝国边界发生变化的唯一方式。此外,每个行政区一旦加入,就永远不会被修改或与其他行政区合并。

矩形帝国最后也是最重要的传统是,确保帝国整体的领土始终是一个矩形,尽管它不一定需要满足单个行政区所要求的 2:1 边长比。

最近,考古学家发现,在某个时间点,帝国的尺寸为 $N \times M$(以 $\Xi$ 为单位)。如果这些数字非常大,你无需惊慌;毕竟,Cartesia 是一个无限平面。你的任务是估算帝国达到此尺寸时的行政区数量。在帝国建立和扩张的所有可能方式中,行政区数量的最小值和最大值分别是多少?

输入格式

输入为一行,包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 10^8$)。

对于 25 分中的 5 分,满足 $N, M \le 1000$。

对于另外 25 分中的 8 分,满足 $N, M \le 10^6$。

输出格式

输出一行,包含行政区数量的最小值,后跟一个空格,再后跟行政区数量的最大值。

样例

输入格式 1

10 6

输出格式 1

5 8

说明

上述样例输出的解释如下。下图展示了如何达到这些最小和最大行政区数量。行政区按添加顺序标记为 #1, #2, #3, ...。每个行政区的尺寸显示在括号中,格式为 $(k \times 2k)$ 或 $(2k \times k)$:

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.