「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)<Q$。

输入输出格式

输入格式


**本题包含多组测试数据。** 第一行,输入一个正整数 $T$,表示有 $T$ 次询问。 对于每次询问: 第一行,输入一个正整数 $op$,表示问题类型。 第二行,若 $op=1$,输入 $2$ 个正整数 $n$ 和 $m$;若 $op=2$,输入 $3$ 个正整数 $n$、$m$ 和 $Q$。

输出格式


共 $T$ 行,对于每次询问:一行输出 $1$ 个正整数,表示对应问题的答案。

输入输出样例

输入样例 #1

2
1
2 3
2
2 3 10

输出样例 #1

4
12

说明

#### 样例解释 #1 对于第一次询问: 下图所示的情况是一种最佳构造方案,梦枫溪穿过 $2 \times 3$ 的网格森林时,最多穿过 $4$ 个小网格(黄色部分为穿过的网格,灰色部分为未穿过的网格)。 ![](https://cdn.luogu.com.cn/upload/image_hosting/7dknua6w.png?x-oss-process=image/resize,m_lfit,h_360) 下示方案不是一种最佳方案,梦枫溪是从两个绿色网格中间的一个顶点上穿过的,所以两个绿色区域都没有被穿过。因此梦枫溪只穿过了 $3$ 个小网格。 ![](https://cdn.luogu.com.cn/upload/image_hosting/cgjzaf2i.png?x-oss-process=image/resize,m_lfit,h_360) 对于第二次询问: 如下图所示,当 $n'=2$, $m'=9$ 时,才能使梦枫溪穿过 $10$ 个网格的情况下,在原基础添加的 $n'm'-nm$ 个网格是最少的(红色虚线左边是原来的森林,右边是添加的部分)。 ![](https://cdn.luogu.com.cn/upload/image_hosting/phkx3o46.png) #### 数据范围 **本题采用 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}$。