Max Weighted Floor of Linear 解説

解説: Max Weighted Floor of Linear

yukicoder で開催されている競技プログラミングコンテスト Advent Calendar Contest 2025 の Day4 (2025-12-04) の問題、 Max Weighted Floor of Linear の解説です。

https://yukicoder.me/problems/12833

問題文

$T$ 個のテストケースがあります。

各テストケースについて、 正の整数 $N,M$ と 整数 $A,B,C,D$ が与えられます。

$\max\left\lbrace Ax+B\left\lfloor\dfrac{Cx+D}{M}\right\rfloor\mathrel{}\middle|\mathrel{} x\in\mathbb{Z},\ 0\leq x\lt N\right\rbrace$ を求めてください。

つまり、整数 $x$ を $0\leq x\lt N$ の範囲で動かした時、 $Ax+B\left\lfloor\dfrac{Cx+D}{M}\right\rfloor$ の式が取りうる値の最大値を求めてください。

制約

• $1 \leq T \leq 10^5$
• $1 \leq N,M \leq 10^9$
• $-10^9 \leq A,B \leq 10^9$
• $0 \leq C,D \lt M$
• 入力される値はすべて整数

解説

• （「正規化」の項目で説明） $0 \leq C,D \lt M$ となるよう正規化し、 $\lfloor(C x+D)/M\rfloor$ が綺麗な階段関数 ( $x=0$ の時に $0$ から始まり、 $x$ が増えるごとに高々 $1$ しか増えない階段関数 ) になるように保ちます
• $y=\lfloor(C x+D)/M\rfloor,\ \mathtt{yMax}=\lfloor(C(N-1)+D)/M\rfloor$ とおきます
• （「区間端点」の項目で説明） 各 $y\in 0,1,\dots,\mathtt{yMax}\rbrace$ を取る区間において最大値を取り得る $x$ を、変数 $y$ を用いて立式します。
  • $y\leq (C x+D)/M\lt y+1$ の不等式を解くと、 $y$ ごとの区間の式を求める事ができます。
  • $\mathtt{yMax}=0$ の時、式はただの一次関数 $Ax$ になるので、両端の値の最大値 $\max(0, A(N-1))$ が答え。
  • $y$ の値を固定した時、 $A\leq 0$ なら 区間の左端 $x=\ell(y)$ が最適。ただし、 $y=0$ の時は $x=0$ が最適な事に注意。
  • $y$ の値を固定した時、 $A\geq 0$ なら 区間の右端 $x=r(y)$ が最適。ただし、 $y=\mathtt{yMax}$ の時は $x=N-1$ が最適な事に注意。
• （「小問題への再帰」の項目で説明） $Ax + By$ の式に、それぞれ最適となる式 $x=\ell(y)$ または $x=r(y)$ を代入すると、元の形の式が現れるので再帰的に処理します。
  • $A \geq 0$ なら、 $y=\mathtt{yMax}\ (x=N-1)$ の場合を分けて、 $0\leq y\lt \mathtt{yMax}$ の区間を再帰的な処理に回した結果の値と、 $y=\mathtt{yMax}\ (x=N-1)$ の場合の値の、最大値が答えです。
  • $A \lt 0$ なら、 $y=0\ (x=0)$ の場合を分けて、 $y=t+1$ のように変数変換を行い、 $0\leq t\lt \mathtt{yMax}$ の区間を再帰的な処理に回した結果の値と、 $y=0\ (x=0)$ の場合の値の、最大値が答えです。

$L\lt R$ および $0\lt M$ を満たす整数 $L,\ R,\ M$ と、任意の整数 $A,\ B,\ C,\ D$ に対して、

$$\mathtt{mwf}(L, R, M, A, B, C, D):=\max\bigg\lbrace \ A x+B\bigg\lfloor\frac{C x+D}{M}\bigg\rfloor\ \biggm\vert\ L\leq x\lt R \ \bigg\rbrace$$

と定義します。

この計算を、以下のような型の上で処理する、非再帰ループもしくは末尾再帰による実装方針を説明します。

$$\mathtt{mwf}(L, R, M, A, B, C, D) = \max(\mathtt{maxAcc}_k,\ \mathtt{sumAcc}_k + \mathtt{mwf}(0, n_k, m_k, a_k, b_k, c_k, d_k))$$

• $\mathtt{maxAcc}_k$ : これまでに求めた端点の最大値
• $\mathtt{sumAcc}_k$ : 定数項の累積和
  • 初期値 $\mathtt{maxAcc}_0 = \mathtt{sumAcc}_0 = A L + B\lfloor (C L + D)/M \rfloor\quad : \quad x = L$ での値
• $n_k,\ m_k,\ a_k,\ b_k,\ c_k,\ d_k$ : 現在の小問題のパラメータ
  • 初期値 $n_0 = R - L,\ m_0 = M,\ a_0 = A,\ b_0 = B,\ c_0 = C,\ d_0 = (C L + D) \bmod M$

$$\begin{aligned} &\max\lbrace Ax+B\lfloor(Cx+D)/M \rfloor \mid L \leq x \lt R \rbrace \newline &= \max\lbrace A (x+L) + B \lfloor (C (x+L) + D)/M \rfloor \mid 0 \leq x \lt (R-L) \rbrace \newline &= AL + B \lfloor (C L + D)/M \rfloor + \max\lbrace A x + B \lfloor (C x + ((C L + D) \bmod M))/M \rfloor \mid 0 \leq x \lt (R-L) \rbrace \newline \end{aligned}$$

この後は、以下のように進めて行きます。

• $Y(x)=\lfloor (cx+d)/m \rfloor$ を階段関数とみて、区間ごとに端点だけ見れば良い状況に簡約する。
• $y \leq Y(x) \lt y+1$ となるような区間 $\ell(y) \leq x \leq r(y)$ の端点 $\ell(y), r(y)$ の式を得る。
• $(m,c)$ がユークリッド互除法的になるような小問題へと再帰的に分解して、効率的に計算する。

正規化

後に述べる「区間端点」「小問題への再帰」の議論と計算を簡単にするため、まずパラメータ $c,\ d$ を正規化します。

任意の整数 $x$ について、

$$\begin{aligned} &\quad a x + b\bigg\lfloor\frac{c x + d}{m}\bigg\rfloor \newline &= a x + b\bigg\lfloor\frac{m\lfloor c / m\rfloor x + m\lfloor d / m\rfloor + (c \bmod m) x + (d \bmod m)}{m}\bigg\rfloor \newline &= b\lfloor d / m\rfloor + (a + b\lfloor c / m\rfloor) x + b\bigg\lfloor\frac{(c \bmod m) x + (d \bmod m)}{m}\bigg\rfloor \newline \end{aligned}$$

が成り立ち、最大化に無関係な定数項 $b \lfloor d / m \rfloor$ を取り出せるので、

• $\mathtt{sumAcc}' = \mathtt{sumAcc} + b \lfloor d / m \rfloor$
• $a' = a + b \lfloor c / m \rfloor$
• $c' = c \bmod m = c - m\lfloor c / m \rfloor \quad (0 \leq c' \lt m)$
• $d' = d \bmod m = d - m\lfloor d / m \rfloor \quad (0 \leq d' \lt m)$

を定めると、

$$\begin{aligned} \mathtt{mwf}(L, R, M, A, B, C, D) &= \max(\mathtt{maxAcc},\ \mathtt{sumAcc} + \mathtt{mwf}(0, n, m, a, b, c, d)) \newline &= \max(\mathtt{maxAcc},\ \mathtt{sumAcc}' + \mathtt{mwf}(0, n, m, a', b, c', d')) \newline \end{aligned}$$

のように変換できます。

以降は、正規化された係数を前提にして考えます。

区間端点

$0 \leq x \lt n$ 上で関数 $Y(x):=\big\lfloor (c' x + d') / m \big\rfloor$ が取りうる最小値は $0$ で、最大値は以下の値 $\mathtt{yMax}$ です。

$$\mathtt{yMax} := \bigg\lfloor \frac{c' (n - 1) + d'}{m} \bigg\rfloor$$

$Y(x)=\big\lfloor (c' x + d')/m \big\rfloor$ は非減少な階段関数です。各 $y\in\lbrace 0,1,\dots,\mathtt{yMax}\rbrace$ に対し、 $Y(x)=y$ を満たす $x$ は連続区間

$$I(y)=\big\lbrace x \in \mathbb{Z} \mid 0 \leq x\lt n,\ y \leq (c' x + d') / m \lt (y + 1) \big\rbrace$$

をなします。

$0 \leq x \lt N$ の区間が $y \in \lbrace 0, 1, \dots, Y'\rbrace$ に対して定まる区間 $I(y)$ ごとに分割されて、 一次関数 $A' x + B y$ が定義されているイメージです。

また、 $c' = 0$ のときは $Y(x) = \lfloor d'/m \rfloor = 0$ で一定で、 $\mathtt{yMax} = 0$ なので、 $I(0) = \lbrace x \in \mathbb{Z} \mid 0 \leq x \lt n \rbrace$ となります。 $\mathtt{yMax} \geq 1$ のときは $0 \lt c' \lt m$ であり、 $Y(x)$ は $x$ が $1$ 変化するごとに高々 $1$ しか変化しない階段関数であるため、 各 $y$ に対して $I(y)$ は空でない区間となります。

したがって $\mathtt{yMax} \geq 1$ の場合、 $I(y)$ の左端 $\ell(y)$ と右端 $r(y)$ は $\lceil u/v \rceil=\lfloor (u+v-1)/v \rfloor \quad (v\gt0)$ の関係式を用いて、

$$\begin{aligned} \ell(y) &= \begin{cases} 0 & (y = 0) \newline \bigg\lceil\dfrac{m y - d'}{c'}\bigg\rceil = \bigg\lfloor\dfrac{m y + c' - d' - 1}{c'}\bigg\rfloor & (0 \lt y \leq \mathtt{yMax}) \end{cases} \newline r(y) &= \begin{cases} \bigg\lfloor\dfrac{m y + m - d' - 1}{c'}\bigg\rfloor & (0 \leq y \lt \mathtt{yMax}) \newline n-1 & (y = \mathtt{yMax}) \end{cases} \end{aligned}$$

また、一次関数 $x\mapsto a' x + b y$ は 区間 $I(y)$ 上で $y$ が固定されるため、

• $a' \geq 0$ のとき 区間 $I(y)$ 上で 一次関数 $x \mapsto a' x + b y$ は非減少であり、 $x = r(y)$ で最大
• $a' \leq 0$ のとき 区間 $I(y)$ 上で 一次関数 $x \mapsto a' x + b y$ は非増加であり、 $x = \ell(y)$ で最大

となります。

小問題への再帰

$$\begin{aligned} \mathtt{yMax} &= \big\lfloor (c' (n - 1) + d') / m \big\rfloor \newline f'(x) &= a' \cdot x + b \big\lfloor (c' \cdot x + d') / m \big\rfloor \newline \mathtt{maxAcc}' &= \max\big(\mathtt{maxAcc},\ \mathtt{sumAcc}' + f'(0),\ \mathtt{sumAcc}' + f'(n-1)\big)\newline &=\max\big(\mathtt{maxAcc},\ \mathtt{sumAcc}',\ \mathtt{sumAcc}' + a'(n-1) + b \cdot \mathtt{yMax}\big) \newline \end{aligned}$$

とすると、次の場合分けが成り立ちます。（場合分けの条件は必ずしも排反とはしていません。判定順は任意です。）

$$\begin{aligned} &\mathtt{mwf}(0, n, m, a', b, c', d') \newline &= {\displaystyle\max_{x\in\mathbb{Z},\ 0\leq x\lt n}}(a' x + b \left\lfloor (c' x + d')/m \right\rfloor) \newline &= \begin{cases} 0 & (1):(a' \leq 0, b \leq 0) \newline a' (n - 1) + b \cdot \mathtt{yMax} & (2):(a' \geq 0, b \geq 0) \newline \max\big(0,\ a' (n - 1)\big) & (3):(\mathtt{yMax} = 0) \newline \max\big((a' (n - 1) + b \cdot \mathtt{yMax}),\ \mathtt{mwf}(0, \mathtt{yMax}, c', b, a', m, (m - d' - 1))\big) & (4):(\mathtt{yMax} \geq 1,\ a' \geq 0) \newline \max\big(0,\ a' + b + \mathtt{mwf}(0,\mathtt{yMax},c',b,a',m,(m-d'-1))\big) & (5):(\mathtt{yMax} \geq 1,\ a' \leq 0) \end{cases} \newline &\mathtt{mwf}(L, R, M, A, B, C, D) \newline &= \max\big(\mathtt{maxAcc},\ \mathtt{sumAcc}' + \mathtt{mwf}(0, n, m, a', b, c', d')\big) \newline &= \max\big(\mathtt{maxAcc}',\ \mathtt{sumAcc}' + \mathtt{mwf}(0, n, m, a', b, c', d')\big) \newline &=\begin{cases} \mathtt{maxAcc}' & (1):(a' \leq 0,\ b \leq 0) \newline \mathtt{maxAcc}' & (2):(a' \geq 0,\ b \geq 0) \newline \mathtt{maxAcc}' & (3):(\mathtt{yMax} = 0) \newline \max\big(\mathtt{maxAcc}',\ \mathtt{sumAcc}' + \mathtt{mwf}(0, \mathtt{yMax}, c', b, a', m, (m - d' - 1))\big) & (4):(\mathtt{yMax} \geq 1,\ a' \geq 0) \newline \max\big(\mathtt{maxAcc}',\ (\mathtt{sumAcc}'+a'+b) + \mathtt{mwf}(0,\mathtt{yMax}, c', b, a', m, (m - d' - 1))\big) & (5):(\mathtt{yMax} \geq 1,\ a' \leq 0) \newline \end{cases} \newline \end{aligned}$$

以下で、それぞれの場合分けについて証明を与えます。

$a' \leq 0,\ b \leq 0$ の場合

$x$ の増加に伴い、 $a' \cdot x$ も $b\bigg\lfloor\dfrac{c' \cdot x + d'}{m}\bigg\rfloor$ も非増加であり、 $a' \cdot x + b \bigg\lfloor\dfrac{c' \cdot x + d'}{m}\bigg\rfloor$ は非増加であるため、 $x = 0$ で最大値 $f'(0)=0$ を取ります。

$a' \geq 0,\ b \geq 0$ の場合

$x$ の増加に伴い、 $a' \cdot x$ も $b \bigg\lfloor\dfrac{c' \cdot x + d'}{m}\bigg\rfloor$ も非減少であり、 $a' \cdot x + b \bigg\lfloor\dfrac{c' \cdot x + d'}{m}\bigg\rfloor$ は非減少であるため、 $x = n - 1$ で最大値 $f'(n - 1)=a'(n - 1) + b \cdot \mathtt{yMax}$ を取ります。

$\mathtt{yMax} = 0$ の場合

このとき $Y(x) = 0$ で一定なので、 $f'(x) = a' \cdot x + b \cdot 0 = a' \cdot x$ となり、 $a' \leq 0$ なら $x = 0$ で最大、 $a' \geq 0$ なら $x = n - 1$ で最大となり、最大値は $\max(0,\ a' (n - 1))$ となります。

$\mathtt{yMax} \geq 1,\ a' \geq 0$ の場合

$a' \geq 0$ なので各 $y$ の最適は $r(y)$ です。 $y = \mathtt{yMax}$ のときは $r(\mathtt{yMax}) = n - 1$ により $f'(n - 1)$ が候補となり、残る $0\leq y\lt \mathtt{yMax}$ の場合を考慮すると

$$\begin{aligned} &\mathtt{mwf}(0, n, m, a', b, c', d') \newline &={\displaystyle\max_{x\in\mathbb{Z},\ 0 \leq x \lt n}}(a' x + b \left\lfloor (c' x + d') / m \right\rfloor) \newline &= {\displaystyle\max_{y\in\mathbb{Z},\ 0 \leq y \leq \mathtt{yMax}}}f'(r(y)) \newline &= \max\bigg(f'(r(\mathtt{yMax})),\ {\displaystyle\max_{y \in \mathbb{Z},\ 0\leq y\lt \mathtt{yMax}}}f'(r(y)) \bigg) \newline &= \max\bigg(f'(n - 1),\ {\displaystyle\max_{y \in \mathbb{Z},\ 0 \leq y \lt \mathtt{yMax}}}\bigg( b y + a' \bigg\lfloor \frac{m y + (m - d' - 1)}{c'} \bigg\rfloor \bigg)\bigg) \newline &= \max\big((a'(n - 1) + b \cdot \mathtt{yMax}),\ \mathtt{mwf}(0, \mathtt{yMax}, c', b, a', m, (m - d' - 1))\big) \newline \end{aligned}$$

$\mathtt{yMax} \geq 1,\ a' \leq 0$ の場合

$a' \leq 0$ なので 各 $y$ の最適は $\ell(y)$ です。 $y = 0$ のときは $\ell(0) = 0$ により $0$ が候補となり、残る $1\leq y\le \mathtt{yMax}$ の場合を考慮して、その後 $u = y - 1$ による変換を行うと

$$\begin{aligned} & \mathtt{mwf}(0, n, m, a', b, c', d') \newline &= {\displaystyle\max_{x\in\mathbb{Z},\ 0 \leq x \lt n}}(a' x + b \left\lfloor (c' x + d') / m \right\rfloor) \newline &= {\displaystyle\max_{y\in\mathbb{Z},\ 0 \leq y \leq \mathtt{yMax}}}f'(\ell(y)) \newline &= \max\bigg(f'(\ell(0)),\ {\displaystyle\max_{y \in \mathbb{Z},\ 1 \leq y \leq \mathtt{yMax}}}f'(\ell(y)) \bigg) \newline &= \max\bigg(f'(0),\ {\displaystyle\max_{y \in \mathbb{Z},\ 1 \leq y \leq \mathtt{yMax}}}\bigg( b y + a' \bigg\lfloor \frac{m y + (c' - d' - 1)}{c'} \bigg\rfloor \bigg)\bigg) \newline &= \max\bigg(0,\ {\displaystyle\max_{u \in \mathbb{Z},\ 0 \leq u \lt \mathtt{yMax}}}\bigg( b (u + 1) + a' \bigg\lfloor \frac{m (u + 1) - d' - 1}{c'} + 1 \bigg\rfloor \bigg)\bigg) \newline &= \max\bigg(0,\ (a' + b)+{\displaystyle\max_{u\in\mathbb{Z},\ 0 \leq u \lt \mathtt{yMax}}}\bigg( b u + a' \bigg\lfloor \frac{m u + (m - d' - 1)}{c'} \bigg\rfloor \bigg)\bigg) \newline &= \max\big(0,\ (a' + b)+\mathtt{mwf}(0, \mathtt{yMax}, c', b, a', m, (m-d'-1))\big) \newline \end{aligned}$$

非再帰での実装例

$$\begin{aligned} &\max\bigg\lbrace A x+B\bigg\lfloor\frac{C x+D}{M}\bigg\rfloor\ \biggm\vert\ L\leq x\lt R \ \bigg\rbrace \newline =& \max(\mathtt{maxAcc}_k,\ \mathtt{sumAcc}_k + \mathtt{mwf}(0, n_k, m_k, a_k, b_k, c_k, d_k)) \end{aligned}$$

の関係が $k=0,1,2,\ldots$ のそれぞれにおいて不変となるように、 「正規化」「小問題への再帰」 に従ってパラメータを更新します。

$$\begin{aligned} & \text{// 擬似コード:}\ \max\Big\lbrace A x+B\cdot\lfloor(Cx+D)/M\rfloor {\ \texttt{for}\ } x {\ \texttt{in}\ } \lbrack L, R \rparen \Big\rbrace \newline & {\texttt{assert}\ } L \lt R {\ \mathtt{and}\ } 0 \lt M \newline & \text{// 初期化} \newline & \left\lbrace\begin{aligned} n_0 &= R - L \newline m_0 &= M \newline a_0 &= A \newline b_0 &= B \newline c_0 &= C \newline d_0 &= (C L + D) \bmod M \newline \mathtt{maxAcc}_0 &= A L + B\cdot\lfloor (C L + D)/M \rfloor \newline \mathtt{sumAcc}_0 &= A L + B\cdot\lfloor (C L + D)/M \rfloor \newline \end{aligned}\right\rbrace \newline & \text{//}\ \max\Big(\mathtt{maxAcc}_k,\ \max\Big\lbrace \mathtt{sumAcc}_k + a_k x+b_k\cdot\lfloor(c_k x+ d_k)/m_k\rfloor {\ \texttt{for}\ } x {\ \texttt{in}\ } \lbrack 0, n_k \rparen \Big\rbrace\Big) \newline & {\texttt{for}\ } k {\ \texttt{in}\ } \lbrack 0, 1, 2, \ldots\rbrack\texttt{:} \newline & \qquad \text{// 正規化、現在の小問題における左端と右端の値で累積最大値更新} \newline & \qquad \left\lbrace\begin{aligned} n'_k &= n_k \newline m'_k &= m_k \newline a'_k &= a_k + b_k \cdot \lfloor c_k/m_k \rfloor \newline b'_k &= b_k \newline c'_k &= c_k \bmod m_k \newline d'_k &= d_k \bmod m_k \newline \mathtt{sumAcc}'_k &= \mathtt{sumAcc}_k + b_k \cdot \lfloor d_k/m_k \rfloor \newline \mathtt{yMax}'_k &= \big\lfloor (c'_k (n_k - 1) + d'_k)/m_k \big\rfloor \newline \mathtt{maxAcc}'_k &= \max(\mathtt{maxAcc}_k,\ \mathtt{sumAcc}'_k,\ \mathtt{sumAcc}'_k + a'_k (n_k - 1) + b'_k \cdot\mathtt{yMax}'_k) \newline \end{aligned}\right\rbrace \newline & \qquad {\mathtt{if}\ } (a'_k \leq 0 {\ \mathtt{and}\ } b'_k \leq 0) {\ \mathtt{or}\ } (a'_k \geq 0 {\ \mathtt{and}\ } b'_k \geq 0) {\ \mathtt{or}\ } (\mathtt{yMax}'_k = 0) \texttt{:} \newline & \qquad\qquad \text{// 現在の小問題において、最大値が左端もしくは右端で確定} \newline & \qquad\qquad \text{// ループ回数を固定とする実装向けのパラメータ更新、必要無ければ省略可} \newline & \qquad\qquad \left\lbrace\begin{aligned} n_{k+1} &= 1 \newline m_{k+1} &= 1 \newline a_{k+1} &= 0 \newline b_{k+1} &= 0 \newline c_{k+1} &= 0 \newline d_{k+1} &= 0 \newline \mathtt{maxAcc}_{k+1} &= \mathtt{maxAcc}'_k \newline \mathtt{sumAcc}_{k+1} &= \mathtt{maxAcc}'_k \end{aligned}\right\rbrace \newline & \qquad\qquad \text{// 確定した最大値を出力して終了} \newline & \qquad\qquad {\texttt{return}\ } \mathtt{maxAcc}'_k \newline & \qquad \texttt{else:} \newline & \qquad\qquad \text{// 小問題へのパラメータ変換} \newline & \qquad\qquad \text{//}\ \mathtt{yMax}'_k \neq 0 \ \text{であれば、}\ 0\lt\mathtt{yMax}'_k=n_{k+1}\lt n_k \ \text{かつ}\ 0\lt c'_k=m_{k+1}\lt m_k \newline & \qquad\qquad \left\lbrace\begin{aligned} n_{k+1} &= \mathtt{yMax}'_k \newline m_{k+1} &= c'_k \newline a_{k+1} &= b'_k \newline b_{k+1} &= a'_k \newline c_{k+1} &= m'_k \newline d_{k+1} &= m'_k - d'_k - 1 \newline \mathtt{maxAcc}_{k+1} &= \mathtt{maxAcc}'_k \newline \mathtt{sumAcc}_{k+1} &= \begin{cases} \mathtt{sumAcc}'_k & (a'_k \geq 0) \newline \mathtt{sumAcc}'_k + a'_k + b'_k & (a'_k \lt 0) \end{cases} \newline \end{aligned}\right\rbrace \newline & \qquad\qquad \text{// 次の反復へ} \newline & \qquad\qquad \texttt{continue}\newline & \qquad \texttt{endif} \newline & \texttt{endfor} \newline \end{aligned}$$

実装例 (PyPy3):

# mwf(L,R,m,a,b,c,d) = max_{x in [L,R)} (a*x + b*floor((c*x + d)/m))
def mwf(L: int, R: int, m: int, a: int, b: int, c: int, d: int) -> int:
    assert L < R and 0 < m
    n = R - L
    qd0, d = divmod(c * L + d, m)
    max_acc = sum_acc = a * L + b * qd0
    while True:
        qc, c = divmod(c, m)
        a += b * qc
        qd, d = divmod(d, m)
        sum_acc += b * qd
        y_max = (c * (n - 1) + d) // m
        max_acc = max(max_acc, sum_acc, sum_acc + a * (n - 1) + b * y_max)
        if (a <= 0 and b <= 0) or (a >= 0 and b >= 0) or y_max == 0:
            return max_acc
        if a < 0:
            sum_acc += a + b
        n, m, a, b, c, d = y_max, c, b, a, m, (m - d - 1)

if __name__ == "__main__":
    import sys
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M, A, B, C, D = map(int, sys.stdin.readline().split())
        print(mwf(0, N, M, A, B, C, D))

テストケースの計算過程

$\mathtt{mwf}(L=0,R=10^9,M=102334155,A=433494437,B=-701408733,C=63245986,D=31415926)$ の計算過程の例を以下に示します。

    　　　　          maxAcc     sumAcc        l      r          m          a          b          c          d
#0  正規化前 : max(         0,         0 + mwf(0,1000000000, 102334155, 433494437,-701408733,  63245986,  31415926))
#0  正規化後 : max(  92488359,         0 + mwf(0,1000000000, 102334155, 433494437,-701408733,  63245986,  31415926))
#1  正規化前 : max(  92488359,         0 + mwf(0, 618033988,  63245986,-701408733, 433494437, 102334155,  70918228))
#1  正規化後 : max( 433494437, 433494437 + mwf(0, 618033988,  63245986,-267914296, 433494437,  39088169,   7672242))
#2  正規化前 : max( 433494437, 599074578 + mwf(0, 381966010,  39088169, 433494437,-267914296,  63245986,  55573743))
#2  正規化後 : max( 433494437, 331160282 + mwf(0, 381966010,  39088169, 165580141,-267914296,  24157817,  16485574))
#3  正規化前 : max( 433494437, 331160282 + mwf(0, 236067976,  24157817,-267914296, 165580141,  39088169,  22602594))
#3  正規化後 : max( 462736810, 331160282 + mwf(0, 236067976,  24157817,-102334155, 165580141,  14930352,  22602594))
#4  正規化前 : max( 462736810, 394406268 + mwf(0, 145898033,  14930352, 165580141,-102334155,  24157817,   1555222))
#4  正規化後 : max( 462736810, 394406268 + mwf(0, 145898033,  14930352,  63245986,-102334155,   9227465,   1555222))
#5  正規化前 : max( 462736810, 394406268 + mwf(0,  90169942,   9227465,-102334155,  63245986,  14930352,  13375129))
#5  正規化後 : max( 462736810, 457652254 + mwf(0,  90169942,   9227465, -39088169,  63245986,   5702887,   4147664))
#6  正規化前 : max( 462736810, 481810071 + mwf(0,  55728088,   5702887,  63245986, -39088169,   9227465,   5079800))
#6  正規化後 : max( 481810071, 481810071 + mwf(0,  55728088,   5702887,  24157817, -39088169,   3524578,   5079800))
#7  正規化前 : max( 481810071, 481810071 + mwf(0,  34441852,   3524578, -39088169,  24157817,   5702887,    623086))
#7  正規化後 : max( 481810071, 481810071 + mwf(0,  34441852,   3524578, -14930352,  24157817,   2178309,    623086))
#8  正規化前 : max( 481810071, 491037536 + mwf(0,  21286234,   2178309,  24157817, -14930352,   3524578,   2901491))
#8  正規化後 : max( 483370049, 476107184 + mwf(0,  21286234,   2178309,   9227465, -14930352,   1346269,    723182))
#9  正規化前 : max( 483370049, 476107184 + mwf(0,  13155615,   1346269, -14930352,   9227465,   2178309,   1455126))
#9  正規化後 : max( 485334649, 485334649 + mwf(0,  13155615,   1346269,  -5702887,   9227465,    832040,    108857))
#10 正規化前 : max( 485334649, 488859227 + mwf(0,   8130616,    832040,   9227465,  -5702887,   1346269,   1237411))
#10 正規化後 : max( 485548358, 483156340 + mwf(0,   8130616,    832040,   3524578,  -5702887,    514229,    405371))
#11 正規化前 : max( 485548358, 483156340 + mwf(0,   5024996,    514229,  -5702887,   3524578,    832040,    426668))
#11 正規化後 : max( 485548358, 483156340 + mwf(0,   5024996,    514229,  -2178309,   3524578,    317811,    426668))
#12 正規化前 : max( 485548358, 484502609 + mwf(0,   3105618,    317811,   3524578,  -2178309,    514229,     87560))
#12 正規化後 : max( 485548358, 484502609 + mwf(0,   3105618,    317811,   1346269,  -2178309,    196418,     87560))
#13 正規化前 : max( 485548358, 484502609 + mwf(0,   1919377,    196418,  -2178309,   1346269,    317811,    230250))
#13 正規化後 : max( 485848878, 485848878 + mwf(0,   1919377,    196418,   -832040,   1346269,    121393,     33832))
#14 正規化前 : max( 485848878, 486363107 + mwf(0,   1186239,    121393,   1346269,   -832040,    196418,    162585))
#14 正規化後 : max( 485866169, 485531067 + mwf(0,   1186239,    121393,    514229,   -832040,     75025,     41192))
#15 正規化前 : max( 485866169, 485531067 + mwf(0,    733135,     75025,   -832040,    514229,    121393,     80200))
#15 正規化後 : max( 486045296, 486045296 + mwf(0,    733135,     75025,   -317811,    514229,     46368,      5175))
#16 正規化前 : max( 486045296, 486241714 + mwf(0,    453101,     46368,    514229,   -317811,     75025,     69849))
#16 正規化後 : max( 486045296, 485923903 + mwf(0,    453101,     46368,    196418,   -317811,     28657,     23481))
#17 正規化前 : max( 486045296, 485923903 + mwf(0,    280031,     28657,   -317811,    196418,     46368,     22886))
#17 正規化後 : max( 486045296, 485923903 + mwf(0,    280031,     28657,   -121393,    196418,     17711,     22886))
#18 正規化前 : max( 486045296, 485998928 + mwf(0,    173068,     17711,    196418,   -121393,     28657,      5770))
#18 正規化後 : max( 486045296, 485998928 + mwf(0,    173068,     17711,     75025,   -121393,     10946,      5770))
#19 正規化前 : max( 486045296, 485998928 + mwf(0,    106961,     10946,   -121393,     75025,     17711,     11940))
#19 正規化後 : max( 486080298, 486073953 + mwf(0,    106961,     10946,    -46368,     75025,      6765,       994))
#20 正規化前 : max( 486080298, 486102610 + mwf(0,     66105,      6765,     75025,    -46368,     10946,      9951))
#20 正規化後 : max( 486080298, 486056242 + mwf(0,     66105,      6765,     28657,    -46368,      4181,      3186))
#21 正規化前 : max( 486080298, 486056242 + mwf(0,     40854,      4181,    -46368,     28657,      6765,      3578))
#21 正規化後 : max( 486080298, 486056242 + mwf(0,     40854,      4181,    -17711,     28657,      2584,      3578))
#22 正規化前 : max( 486080298, 486067188 + mwf(0,     25249,      2584,     28657,    -17711,      4181,       602))
#22 正規化後 : max( 486080298, 486067188 + mwf(0,     25249,      2584,     10946,    -17711,      1597,       602))
#23 正規化前 : max( 486080298, 486067188 + mwf(0,     15604,      1597,    -17711,     10946,      2584,      1981))
#23 正規化後 : max( 486080298, 486078134 + mwf(0,     15604,      1597,     -6765,     10946,       987,       384))
#24 正規化前 : max( 486080298, 486082315 + mwf(0,      9643,       987,     10946,     -6765,      1597,      1212))
#24 正規化後 : max( 486080298, 486075550 + mwf(0,      9643,       987,      4181,     -6765,       610,       225))
#25 正規化前 : max( 486080298, 486075550 + mwf(0,      5959,       610,     -6765,      4181,       987,       761))
#25 正規化後 : max( 486080298, 486079731 + mwf(0,      5959,       610,     -2584,      4181,       377,       151))
#26 正規化前 : max( 486080298, 486081328 + mwf(0,      3682,       377,      4181,     -2584,       610,       458))
#26 正規化後 : max( 486080298, 486078744 + mwf(0,      3682,       377,      1597,     -2584,       233,        81))
#27 正規化前 : max( 486080298, 486078744 + mwf(0,      2275,       233,     -2584,      1597,       377,       295))
#27 正規化後 : max( 486080341, 486080341 + mwf(0,      2275,       233,      -987,      1597,       144,        62))
#28 正規化前 : max( 486080341, 486080951 + mwf(0,      1405,       144,      1597,      -987,       233,       170))
#28 正規化後 : max( 486080675, 486079964 + mwf(0,      1405,       144,       610,      -987,        89,        26))
#29 正規化前 : max( 486080675, 486079964 + mwf(0,       867,        89,      -987,       610,       144,       117))
#29 正規化後 : max( 486080675, 486080574 + mwf(0,       867,        89,      -377,       610,        55,        28))
#30 正規化前 : max( 486080675, 486080807 + mwf(0,       535,        55,       610,      -377,        89,        60))
#30 正規化後 : max( 486080675, 486080430 + mwf(0,       535,        55,       233,      -377,        34,         5))
#31 正規化前 : max( 486080675, 486080430 + mwf(0,       330,        34,      -377,       233,        55,        49))
#31 正規化後 : max( 486080675, 486080663 + mwf(0,       330,        34,      -144,       233,        21,        15))
#32 正規化前 : max( 486080675, 486080752 + mwf(0,       203,        21,       233,      -144,        34,        18))
#32 正規化後 : max( 486080752, 486080752 + mwf(0,       203,        21,        89,      -144,        13,        18))
#33 正規化前 : max( 486080752, 486080752 + mwf(0,       125,        13,      -144,        89,        21,         2))
#33 正規化後 : max( 486080752, 486080752 + mwf(0,       125,        13,       -55,        89,         8,         2))
#34 正規化前 : max( 486080752, 486080786 + mwf(0,        76,         8,        89,       -55,        13,        10))
#34 正規化後 : max( 486080752, 486080731 + mwf(0,        76,         8,        34,       -55,         5,         2))
#35 正規化前 : max( 486080752, 486080731 + mwf(0,        47,         5,       -55,        34,         8,         5))
#35 正規化後 : max( 486080765, 486080765 + mwf(0,        47,         5,       -21,        34,         3,         0))
#36 正規化前 : max( 486080765, 486080778 + mwf(0,        27,         3,        34,       -21,         5,         4))
#36 正規化後 : max( 486080765, 486080757 + mwf(0,        27,         3,        13,       -21,         2,         1))
#37 正規化前 : max( 486080765, 486080757 + mwf(0,        17,         2,       -21,        13,         3,         1))
#37 正規化後 : max( 486080765, 486080757 + mwf(0,        17,         2,        -8,        13,         1,         1))
#38 正規化前 : max( 486080765, 486080762 + mwf(0,         8,         1,        13,        -8,         2,         0))
#38 正規化後 : max( 486080765, 486080762 + mwf(0,         8,         1,        -3,        -8,         0,         0))

#38 の正規化後の段階で、

• $a\lt 0$ かつ $b\lt 0$
  • 非増加関数となるため、右端点の値のみが候補
• $\ell\leq x\lt r$ の区間において $0=\lfloor(cx+d)/m\rfloor$
  • 床関数の中身が $0$ であるため、両端点の値のみが候補

の2条件を満たします。（どちらか一方だけでも終了条件を満たします）

両端点の値は正規化するごとに maxAcc に反映済みであり、これ以上の最大値が得られる見込みがないため、 maxAcc の値 $486080765$ で出力するべき値は確定します。

計算量

正規化により常に $0 \leq c', d' \lt m$ が保たれ、 $\mathtt{yMax} = \lfloor (c'(n - 1) + d') / m \rfloor = 0$ でループが終了します。 $\mathtt{yMax} = \lfloor (c'(n - 1) + d') / m \rfloor \geq 1$ の場合に現れる再帰は、分母パラメータが再帰と正規化によって $(m, c')\mapsto (c', (m \bmod c'))$ にユークリッド互除法型の縮約が起きます。

補足: ユークリッド互除法の計算量

ユークリッドの互除法では、与えられた整数 $a \geq b \gt 0$ に対して次の操作を、 $(a \bmod b) = 0$ となるまで繰り返します：

$$(a,\ b)\mapsto (b,\ a \bmod b)$$

ここで、 $1$ 回の操作で得られる余りを $c := a \bmod b$ とおきます。このとき、余りの定義から常に $0 \leq c \lt b$ が成り立ちます。

次に、余り $c = a \bmod b$ が常に $a / 2$ 未満であることを示します。

• もし $b \leq (a / 2)$ なら:
  • このとき $c \lt b \leq (a / 2)$ より $c \lt (a / 2)$ が成り立ちます。
• もし $b \gt (a / 2)$ なら:
  • このとき $1 \leq (a / b) \lt 2$ なので $\lfloor a / b \rfloor = 1$ です。
  • 除法の等式 $(a \bmod b) = a - b \lfloor a / b \rfloor$ より $c = a - b$ です。
  • したがって $c = a - b \lt a - (a / 2) = (a / 2)$ が成立します。
• 以上より、いずれの場合も $0 \leq c \lt (a / 2)$ が成り立ちます。

したがって:

• 互除法の1回の操作で、分母パラメータは常に減少します。 $0 \leq (a \bmod b) \lt b$ であるため。
• 互除法の2回の操作で、分母パラメータは確実に半分以下になります。 $0 \leq (a \bmod b) \lt (a / 2)$ であるため。
• よって互除法は分母が指数関数的に減少し、高々 $(2 \lfloor \log_{2} b \rfloor + 1)$ 回の操作で、余りが $0$ となり終了します。
  • ラメの定理とフィボナッチ数列の性質により、互除法の反復回数のより正確な上限は、黄金比 $\varphi = (1 + \sqrt{5}) / 2 \approx 1.618$ を用いて $(\lfloor\log_{\varphi} b \rfloor+1)$ 回とも表せますが、詳細は省略します。
• 以上より、互除法の反復回数は $\mathcal{O}(\log b)$ 、もしくは緩めに $\mathcal{O}(\log a)$ と言えます。

遅くとも、余り $c'$ が $0$ になると $\mathtt{yMax} = \lfloor (c'(n - 1) + d') / m \rfloor = 0$ となりループが終了します。

各反復を（多倍長の四則演算の影響を無視して） $\mathcal{O}(1)$ 時間で実行できると見なすと、全体の計算量は反復回数の上限に依存し、 $\mathcal{O}(\log M)$ と言えます。

補足: Min of Mod of Linear との関連

例えば、 Min of Mod of Linear は本問題の解法を用いて解けます。

• Max Weighted Floor of Linear （この問題）
  
  $$\mathtt{mwf}(L,R,M,A,B,C,D)=\max\left\lbrace Ax+B\left\lfloor\dfrac{Cx+D}{M}\right\rfloor\mathrel{\Bigg\vert}x\in\mathbb{Z},\ L\leq x\lt R\right\rbrace$$
• Min of Mod of Linear
  
  $$\begin{aligned}\mathtt{minmod}(L,R,M,A,B)&=\min\left\lbrace (Ax+B)\bmod M \mid x\in\mathbb{Z},\ L\leq x\lt R\right\rbrace \newline &= \min\left\lbrace (Ax+B)-M\left\lfloor\dfrac{Ax+B}{M}\right\rfloor \mathrel{\Bigg\vert} x\in\mathbb{Z},\ L\leq x\lt R\right\rbrace \newline &= B-\max\left\lbrace -Ax+M\left\lfloor\dfrac{Ax+B}{M}\right\rfloor \mathrel{\Bigg\vert} x\in\mathbb{Z},\ L\leq x\lt R\right\rbrace \newline \mathtt{minmod}(L,R,M,A,B) &= B-\mathtt{mwf}(L,R,M,-A,M,A,B) \newline \end{aligned}$$

def min_of_mod_of_linear(L: int, R: int, m: int, a: int, b: int) -> int:
    """
    min_{L <= x < R} ( (a*x + b) % m ) を計算して返す。

    (a*x + b) % m
      = a*x + b - m * floor((a*x + b)/m)
      = b - ( -a*x + m*floor((a*x + b)/m) )

    これは b - mwf(L, R, m, -a, m, a, b) を求める問題に帰着する。
    前提: L < R, 0 < m
    https://judge.yosupo.jp/problem/min_of_mod_of_linear
    """
    assert L < R and 0 < m
    return b - mwf(L, R, m, -a, m, a, b)