P9552 「CROI · R1」浣熊的小溪

> “从太阳里奔来，又迎着阳光走去；张开熊爪，与风相拥，离别之际，却低首自吟。”\ 那梦枫畔嬉戏的成长，那阳光下不羁的信仰，历久弥坚，在无数浣熊的心畔回响。 \ > 可叹，灵溪上畔，一人意志，大小工事，割裂了纯真的年华，刀刻了落寞的隔阂。\ 那明澈的小溪，那快乐的往日，还会，在感怀中驻足吗……

浣熊岭的森林可以看作一张 $n \times m$ 的网格图。工厂排放的废水污染了纵贯森林的梦枫溪（一条直线），导致所经区域对浣熊是有害的。小浣熊 CleverRaccoon 为了研究废水对浣熊的危害，要寻求你的帮助。 设 $f(n,m)$ 表示一条直线最多能穿过 $n\times m$ 的网格图的格子数。 小浣熊有两种问题想要问你： 1. 给定 $n,m$，求 $f(n,m)$； 2. 给定 $n,m,Q$，你需要找到 $n'\ge n,m'\ge m$，满足 $f(n',m')\ge Q$，且 $n'\times m'$ 尽可能小。求 $n'm'-nm$ 的最小值**对 $998244353$ 取模**的结果。数据保证 $f(n,m)

无

无

#### 样例解释 #1 对于第一次询问： 下图所示的情况是一种最佳构造方案，梦枫溪穿过 $2 \times 3$ 的网格森林时，最多穿过 $4$ 个小网格（黄色部分为穿过的网格，灰色部分为未穿过的网格）。  下示方案不是一种最佳方案，梦枫溪是从两个绿色网格中间的一个顶点上穿过的，所以两个绿色区域都没有被穿过。因此梦枫溪只穿过了 $3$ 个小网格。  对于第二次询问： 如下图所示，当 $n'=2$, $m'=9$ 时，才能使梦枫溪穿过 $10$ 个网格的情况下，在原基础添加的 $n'm'-nm$ 个网格是最少的（红色虚线左边是原来的森林，右边是添加的部分）。  #### 数据范围 **本题采用 Subtask 捆绑测试。** | Subtask | $n$ | $m$ | $Q$ | 特殊性质 | Score | | :-: | :-: | :-: | :-: | :-: | :-: | | $0$ | $\le10^{18}$ | $=1$ | $\le2 \times 10^{18}$ | $op=1$ | $5$ | | $1$ | $\le10^{18}$ | $=1$ | $\le2 \times 10^{18}$ | $op=2$ | $5$ | | $2$ | $\le10^{18}$ | $\le10^{18}$ | $\le2 \times 10^{18}$ | $op=1$ | $25$ | | $3$ | $\le10^{18}$ | $\le10^{18}$ |$\le2 \times 10^{18}$ | $op=2$ | $25$ | | $4$ | $\le10^9$ | $\le10^9$ | $\le2 \times 10^9$ | 无特殊性质 | $30$ | | $5$ | $\le10^{18}$ | $\le10^{18}$ | $\le2 \times 10^{18}$ | 无特殊性质 | $10$ | 对于 $100\%$ 的数据，保证 $1 \le T \le 10$，$op \in \{1,2\}$，$1 \le n,m \le 10^{18}$，$2 \le n+m \le Q \le 2 \times 10^{18}$。