P9552 "CROI · R1" Raccoon’s Stream

> "Coming from the sun, and walking into the sunlight; spreading bear paws, embracing the wind, yet at farewell, lowering the head to sing to oneself."\ That playful growth by the Dream Maple shore, that unrestrained belief under the sun, has grown stronger with time, echoing in the hearts of countless raccoons.\ > Sadly, along the upper Ling Stream, one person’s will and various constructions have torn apart the innocent years, carving a lonely barrier.\ That clear little stream, those happy days of the past—will they still make one stop in remembrance...

The forest of Raccoon Ridge can be viewed as an $n \times m$ grid. Wastewater discharged by a factory has polluted the Dream Maple Stream (a straight line) that runs through the forest, making the regions it passes through harmful to raccoons. The little raccoon CleverRaccoon, in order to study the harm caused by the wastewater, seeks your help. Let $f(n,m)$ denote the maximum number of cells that a straight line can pass through in an $n \times m$ grid. The little raccoon has two kinds of questions to ask you: 1. Given $n,m$, find $f(n,m)$. 2. Given $n,m,Q$, you need to find $n'\ge n, m'\ge m$ such that $f(n',m')\ge Q$, and $n'\times m'$ is as small as possible. Output the minimum value of $n'm'-nm$ **modulo $998244353$**. The testdata guarantees that $f(n,m)

**This problem contains multiple test cases.** The first line contains a positive integer $T$, indicating that there are $T$ queries. For each query: The first line contains a positive integer $op$, indicating the type of the question. The second line: if $op=1$, input $2$ positive integers $n$ and $m$; if $op=2$, input $3$ positive integers $n$, $m$, and $Q$.

Output $T$ lines. For each query, output one positive integer on a single line, representing the answer to the corresponding question.

#### Sample Explanation #1 For the first query: The situation shown in the figure below is an optimal construction. When the Dream Maple Stream passes through a $2 \times 3$ grid forest, it can pass through at most $4$ small cells (the yellow parts are the cells it passes through, and the gray parts are the cells it does not pass through).  The construction below is not optimal. The Dream Maple Stream passes through a vertex between two green cells, so neither of the two green regions is counted as being passed through. Therefore, the Dream Maple Stream passes through only $3$ small cells.  For the second query: As shown in the figure below, only when $n'=2$, $m'=9$ can the added number of cells $n'm'-nm$ be minimized while making the Dream Maple Stream pass through $10$ cells (the left side of the red dashed line is the original forest, and the right side is the added part).  #### Constraints **This problem uses bundled Subtask testdata.** | Subtask | $n$ | $m$ | $Q$ | Special Property | 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$ | No special property | $30$ | | $5$ | $\le10^{18}$ | $\le10^{18}$ | $\le2 \times 10^{18}$ | No special property | $10$ | For $100\%$ of the data, it is guaranteed that $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}$. Translated by ChatGPT 5