この記事は新歓ブログリレー2026 51日目の記事です。

ちなみに、$2251799813685248=2^{51}$ です。

このブログで使用する記号について

実数 $x$ に対して、$\lfloor x\rfloor$ は、$x$ 以$下$の最$大$の整数を表すものとします。
また、実数 $x$ に対して、$\lceil x\rceil$ は、$x$ 以$上$の最$小$の整数を表すものとします。

このブログの内容について

このブログでは以下の $2$ つの値を $O(\log B)$ で求める方法を図を用いて紹介します。どちらもサンプルコードを用意しているので、もしコンテスト中の方がいればコピペして使えます。だたし、コピペする場合は赤字の部分に注意してください。

1. $\sum _{i=0}^N\lfloor \frac{Ci+D}{B}\rfloor$
2. $\underset{0\le i\le N}{\max }(A\lfloor \frac{Ci+D}{B}\rfloor +Ei+F)$

重要
以下のサンプルコードはusing ll = long long;及びこのfloor2関数を前提としています。利用する場合はこちらも忘れずにコピペしてください。

/// @brief 有理数のfloorを求める
/// @param y
/// @param x 
/// @return floor(y/x)
ll floor2(ll y, ll x){
    if ((x^y) > 0){
        x = abs(x);
        y = abs(y);
        return y/x;
    }
    else if ((x^y) < 0){
        x = abs(x);
        y = abs(y);
        return -((y+x-1)/x);
    }
    else{
        return y/x;
    }
}

1と2のサンプルコードはこちら

//floor_sum関数に4つの整数N,B,C,Dをこの順で渡してください。
//正常に動作することが保証される範囲は、N<=10^9, -10^9<=B,C,D<=10^9, B!=0です。

ll internal_floor_sum(ll A, ll B, ll C){
    if (C < 0){return 0;}
    if (A > B){return internal_floor_sum(B,A,C);}
    if (B%A == 0){
        return (1+floor2(C,A))*(1+floor2(C,B)) - (B/A)*floor2(C,B)*(floor2(C,B)+1)/2;
    }
    ll k = floor2(C-B*floor2(C,B),A);
    return (1+k)*(1+floor2(C,B)) + floor2(B,A)*floor2(C,B)*(floor2(C,B)+1)/2 + internal_floor_sum(A, B%A, C-A*(floor2(B,A)*floor2(C,B)+k+1));
}
/// @brief `\sum_{i=0}^{N} \lfloor\frac{Ci+D}{B}\rfloor`を求める。
/// @param N 
/// @param M 
/// @param A 
/// @param B 
/// @return 
ll floor_sum(ll N, ll B, ll C, ll D){
    if (N < 0){
        return 0;
    }
    if (B < 0){//Bを負にする。
        B *= -1;
        C *= -1;
        D *= -1;
    }
    if (C > 0){//Cを負にするが、Cを-Cに置き換えてC>0として扱う。
        D += N*C;
    }
    else{
        C *= -1;
    }
    if (C == 0){
        return (N+1)*floor2(D,B);
    }
    ll k = floor2(D-C*N,B);
    return (N+1)*k + internal_floor_sum(B,C,D-B*(k+1));
}

//floor_max関数に7つの整数N,A,B,C,D,E,Fをこの順で渡してください。
//正常に動作することが保証される範囲は、0<=N, -10^9<=A,B,C,D,E,F<=10^9, B!=0です。


ll internal_floor_max(ll A, ll B, ll C, ll D, ll E, ll F){
    if (D < 0){return -1000000000000000000;}
    if (C <= 0){return -1000000000000000000;}
    if (E > 0){
        if (B > C){swap(A,E);swap(B,C);}
        ll M = floor2(D-C*floor2(D, C), B);
        ll tempans = max(A*M+E*floor2(D, C), A*floor2(D, B)) + F;
        return max(tempans, A*(1+M)+internal_floor_max(A, B, C%B, D-B*(1+M+floor2(C, B)*floor2(D, C)), E-A*floor2(C, B), F+A*floor2(C, B)*floor2(D, C)));
    }
    else return A*floor2(D, B) + F;
}

/// @brief `0<=x<=N`の下で、`A*floor2(C*x+D, B)+E*x+F`の最大値を求める。もし何かがおかしいなら`-10^18`が返される。
/// @param N 
/// @param A 
/// @param B 
/// @param C 
/// @param D 
/// @param E 
/// @param F 
/// @return `max`
ll floor_max(ll N, ll A, ll B, ll C, ll D, ll E, ll F){
    if (N < 0){
        return -1000000000000000000;
    }
    assert(B != 0);
    //マイナスを処理
    if (B < 0){
        B *= -1;
        C *= -1;
        D *= -1;
    }
    if (A < 0){
        A *= -1;
        C *= -1;
        D *= -1;
        D += B-1;
    }
    //自明なケース
    if (C == 0 or A == 0){
        return A*floor2(D, B) + F + max(0LL, E*N);
    }
    if (E == 0){
        return A*floor2(max(0LL, C*N)+D, B) + F;
    }
    //Cの係数を調整
    if (C > 0){
        F += E*N;
        E *= -1;
        D += C*N;
    }
    else{
        //`A*floor2(D-C*x, B)+E*x+F`, `A,B,C>0`にする
        C *= -1;
    }
    //自明なケースを処理
    if (E < 0){
        return A*floor2(D, B) + F;
    }
    ll x_offset = floor2(D-C*N, B)+1;
    D -= B*x_offset;
    return A*x_offset + max(internal_floor_max(A,B,C,D,E,F), -A+E*N+F);
}

1について

$\sum _{i=0}^N\lfloor \frac{Ci+D}{B}\rfloor$ という形はfloor sumと呼ばれていて、知っている人も多いと思います。しかし、これを $O(\log B)$ で計算するとなると、その過程で数式を色々いじる必要があり、何が起きているかが分かりにくいです。そのため、$xy$平面上のある領域内の格子点を数える問題に帰着させ、それを図を用いて説明することにします。最後に動画があるので、それだけを見ても何となく理解できると思います。

まず、シグマの形は扱いづらいので、これを変形します。多少は数式をいじりますが、直感的な説明も載せておきます。

まず、$B$ が負のときは分母と分子に $-1$ を掛けます。
次に、$C$ が正のときは $i=0,1,2,...,N$ ではなく、$i=N,N-1,N-2,...,1$ のように、逆から足します。( $i$ を $N-i$ に置き換えます。)すると、$C$ は $0$ 以下になります。
また、$C=0$ のときはシグマの中身が定数となり、簡単に計算できるので、$C\ne 0$ としても問題ないことが分かります。
以上より、$B>0,C<0$ を仮定できます。$C$ が負であると扱いづらいので、以下では $C$ を $-C$ に置き換え、$C>0$ とします。
この時点で、対象の式は $\sum _{i=0}^N\lfloor \frac{D-Ci}{B}\rfloor$ と変形されることに注意してください。
次に、定数 $k=\lfloor \frac{D-CN}{B}\rfloor$ を用いて以下のように変形します。
$\sum _{i=0}^N\lfloor \frac{D-Ci}{B}\rfloor =\sum _{i=0}^N(\lfloor \frac{D-Ci}{B}\rfloor -k+k)=(N+1)k+\sum _{i=0}^N(\lfloor \frac{D-Ci}{B}\rfloor -k)=(N+1)k+\sum _{i=0}^N\lfloor \frac{D-Bk-Ci}{B}\rfloor$
このとき、シグマの部分は平面上の領域 $\{(x,y)|Bx+Cy\le D-Bk,0\le y,1\le x\}$ の内部と境界上に存在する格子点の個数を表します。

領域の境界が $1\le x$ だと扱いにくいので、x軸正方向に $-1$ だけ平行移動し、$\{(x,y)|Bx+Cy\le D-B(k+1),0\le y,0\le x\}$ とします。

以上のことから、floor sumは、$3$ つの定数 $A>0,B>0,C$ を用いた領域 $\{(x,y)|Ax+By\le C,0\le x,0\le y\}$ の内部及び境界上の格子点を数える問題に帰着されることが示されました。

三角形領域内の格子点の数え上げ

三角形領域$(\{(x,y)|Ax+By\le C,0\le x,0\le y\})$ 内の格子点を $\sum _{i=0}^{N}i=\frac{1}{2}N(N+1)$ のような総和公式を用いて一瞬で求めることはできません。そのため、求められる部分から順次切り取っていくようにします。
以下では、三角形領域の境界線である直線 $Ax+By\le C$ のことを直線 $L$ とします。

具体的には以下の手順を、終了と言われるまで繰り返します。

1. もし、$C$ が負なら終了する。
2. もし、$A>B$ なら $A$ と $B$ を入れ替える。
3. もし、$B$ が $A$ の倍数なら、格子点の個数は $\sum _{i=0}^{\lfloor \frac{C}{B}\rfloor }(1+\lfloor \frac{C-Bi}{A}\rfloor )=\sum _{i=0}^{\lfloor \frac{C}{B}\rfloor }(1+\lfloor \frac{C}{A}\rfloor -\frac{B}{A}i)$ となり、これは総和公式で一瞬で求まる。操作を終了する。
4. そうでないなら、三角形領域 $(\{(x,y)|x\le -\lfloor \frac{B}{A}\rfloor (y-\lfloor \frac{C}{B}\rfloor ),0\le x,0\le y\})$ 内(境界を含む)の格子点の個数を求め(ステップ3のようにすることで簡単に求まる)、これを答えに加算する。そのあと、$(x\mapsto x-\lfloor \frac{B}{A}\rfloor (y-\lfloor \frac{C}{B}\rfloor ),y\mapsto y)$ と変換して境界線 $L$ をせん断変形する。そのあと、長方形領域 $(0\le y\le \lfloor \frac{C}{B}\rfloor ,1\le x\le \lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor )$ 内(境界を含む)の格子点の数を掛け算で求めて答えに加算する。最後に、$L$ を $x$ 軸正方向に $-(1+\lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor )$ だけ平行移動する。
   ステップ4全体としては、$A,B,C$ はそれぞれ $A,B-A\lfloor \frac{B}{A}\rfloor ,C-A(\lfloor \frac{B}{A}\rfloor \lfloor \frac{C}{B}\rfloor +\lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor +1)$ に置き換えられることになる。

これだけだとよく分からないので、図を出して説明していきます。

1について

もし、$C$ が負の場合は領域が存在しないため、そのまま終了します。

2について

もし、三角形領域が縦長の場合、$A$ と $B$ を入れ替えて横長にします。この操作は、直線 $y=x$ に関して対称移動を行うだけなので、領域内の格子点の数は変わりません。

3について

$B$ が $A$ の倍数のとき、$y$ 座標を固定して数え上げるとシグマの中身は等差数列になるので、総和公式で簡単に求めることができます。

4について

これが一番重要です。
簡単に数えられる中で最大の三角形をとります。つまり、以下の図で、「青線の傾きの逆数が整数になる範囲で、青線の傾きが赤線の傾きを超えない最大」であり、「青線の $y$切片が最大」であるものを選択します。
青線の傾きの逆数が整数でなければならない理由は、後述するシグマの中身を等差数列にするためです。

上の図は、$A=6,B=16,C=79$ です。(これ以降もこの具体例で説明します) また、青線の $y$切片は最大の $4$ に固定し、青線の傾きは $-1,-\frac{1}{2},-\frac{1}{3},-\frac{1}{4},-\frac{1}{5},-\frac{1}{6}$ の $6$ 通りを示しています。赤線の傾きは $-\frac{3}{8}$ なので、これを超えない最大の傾きは $-\frac{1}{2}$ となります。

次に、青線と $x$ 軸と $y$ 軸で囲まれた領域内(境界を含む)の格子点の個数を求めます。

図に書かれている通り、青線と $x$ 軸と $y$ 軸で囲まれた領域内(境界を含む)の格子点の個数は $25$ 個となります。この値は答えに加算しておきます。

次に、青線がy軸に重なるように平面上にあるすべての図形をせん断変形します。
すなわち、$x$ を $x-\lfloor \frac{B}{A}\rfloor (y-\lfloor \frac{C}{B}\rfloor )$ に置き換えます。変形のイメージは以下の図で示します。

実際に変形を行うと、以下のような図になります。(点線がせん断変形前の状態)

また、先ほど数えなかった点が存在する範囲は以下の画像のように変化します。青の点線上の点はすでに数えていることに注意してください。(紫色が変形前, 赤色が変形後)

重要
せん断変形前の格子点と、せん断変形後の格子点は $1$ 対 $1$ で対応するため、紫の領域内(境界を含む)と赤の領域内(境界を含む)の格子点の数は等しくなります。

次に、せん断変形後の赤い領域において数えるべき残りの点を、長方形領域内の点と三角形領域内の点に分割すると、以下の画像のようになります。

左側の方の長方形領域の内部及び境界上に存在する格子点の個数は $10$ 個です。
そして、(点線でない)赤い線を $x$ 軸正方向に $-3$ だけ移動することで、右側の三角形領域の内部(境界を含む)の格子点の個数は、「(傾きが負の有理数の)直線と、$x$ 軸と、$y$ 軸に囲まれた領域の内部(境界を含む)の格子点の個数」と等しくなるので、これは最初と同じ状態になります。したがって、ステップ1からやり直すことで、再帰的にこの問題を解くことができます。

計算量解析

ステップ $4$ にある通り、手順を1からやり直すたびに $3$ つの定数 $A,B,C$ はそれぞれ $A,B-A\lfloor \frac{B}{A}\rfloor ,C-A(\lfloor \frac{B}{A}\rfloor \lfloor \frac{C}{B}\rfloor +\lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor +1)$ に置き換えられることになります。$C$ はかなり複雑に変化しますが、$A$ と $B$ に着目すると、$A$ はそのままで、$B$ は $B-A\lfloor \frac{B}{A}\rfloor =(BをAで割ったあまり)$ に変化していることになります。そして、ステップ $2$ では $A\le B$ となるように $A$ と $B$ を交換することになり、終了条件の $1$ つも「 $B$ が $A$ の倍数」となっているので、これは正整数 $A$, $B$ に対してユークリッドの互除法を適用する過程と全く同じとなります。
したがって、時間計算量は $O(\log A)$ となりますが、このパラメーター $A$ は本来のfloor sumでは $B$ であったので、floor sum自体の時間計算量は $O(\log B)$ となります。

図形的なイメージとしては、直線の傾きを、急な状態と緩やかな状態の間で交互に変化させ、各ステップでは三角形の面積( $\approx$ 格子点の個数)を約半分以下にしていることになるので、時間計算量は対数時間になることが分かると思います。下に図を載せておきます。
最初、黒線があるとき、各ステップによって、黒→赤→青→緑→紫→橙のように直線が変化していきます。(ただし、実際には傾きが急な直線(赤, 緑, 橙)は、直線 $y=x$ に関して対称な位置に移動して扱います。)
この図は $A=21,B=34$ です。

動画による説明

これまでのステップ $1$ ～ステップ $4$ をまとめたアニメーション動画を $2$ 通り用意しました。図がよくわからなくても多分大体の雰囲気は分かると思います。この動画では、ステップ $4$ の青領域内(境界を含む)の格子点と、せん断変形後の図の左側の長方形領域内(境界を含む)の格子点をまとめてカウントしています。

実装について

基本形のfloor sumを格子点の数え上げ問題に帰着した後、ステップ $1$ ~ $4$ をそのまま再帰関数またはwhile文として実装すればいいです。実装例はこのブログの上部にあります。

2について

$\underset{0\le i\le N}{\max }(A\lfloor \frac{Ci+D}{B}\rfloor +Ei+F)$ という形は、あまり有名ではないかもしれませんが、これもfloor sumと同じように $O(\log B)$ で求めることができます。数式をいじる方法は難しいというか、わからなかったため、これも先ほどと同じように平面上の格子点に関する問題に帰着させて解きます。

floor sumと比べて多少数式が増えるかもしれません。

まず、$A>0,B>0,C<0,E>0$ としても問題ないことを示します。
$A=0$ または $C=0$ または $E=0$ のときは、単調増加または単調減少となるため、両端を試し、大きい方を答えにすればいいです。
$B<0$ のときは、分母と分子に $-1$ を掛ければ $B>0$ となります。
$A<0$ のときは、$A\lfloor \frac{Ci+D}{B}\rfloor =-A\lceil \frac{-Ci-D}{B}\rceil =-A\lfloor \frac{-Ci-D+B-1}{B}\rfloor$ となるため、$C\mapsto -C,D\mapsto -D+B-1$ とすることで、$A>0$ としても問題ないことが分かります。
$C>0$ のときは、$i$ を $N-i$ に置き換えることで、$C<0$ にできます。
$E<0$ のときは、上記の過程より、$A\lfloor \frac{Ci+D}{B}\rfloor$ は単調減少なので、全体としても単調減少になります。よって、$i=0$ の時の値が答えになります。よって、$E>0$ としても問題ないです。

以上より、$A>0,B>0,C<0,E>0$ としても問題ないことが示せました。
そして、floor sumの時と同様に $C$ を $-C$ に置き換え、 $C>0$ とします。

この時点で、対象の式は $\underset{0\le i\le N}{\max }(A\lfloor \frac{D-Ci}{B}\rfloor +Ei+F)\{A,B,C,E>0\}$ となっていることに注意してください。

ここで、次の言い換えを行います。
$\lfloor \frac{D-Ci}{B}\rfloor$ は、「平面上の格子点 $(x,y)$ が $y=i,Bx+Cy\le D$ を満たすときの $x$ の取りうる値の最大値」となります。
実際に具体的に点 $(\lfloor \frac{D-Ci}{B}\rfloor ,i)$ を図示してみると以下のようになります。以下の図は $B=6,C=16,D=79,N=7$ であり、赤線が直線 $Bx+Cy=D$ です。

最大化する対象の式は $A\lfloor \frac{D-Ci}{B}\rfloor +Ei+F$ であるので、さらに言い換えると、この問題は、「点 $(x,y)$ が上記の画像の青い点上のみに存在するとき、$Ax+Ey+F$ の最大値を求める問題」に帰着させることができます。
以下では、$Ax+Ey+F=T$ と置き、$T$ の最大値を求めていきます。

このままでは点の $x$ 座標が負になることがあり、扱いづらいため、最も $y$ 座標の大きい点の $x$ 座標がちょうど $-1$ になるように $x$ 軸方向に平行移動します。上の図では $x$ 軸正方向に $5$ だけ平行移動することになります。これにより、赤線の方程式は $6x+16y=109$ となります。ただし、平行移動を行ったことで、答えとなる $T$ の最大値が $A\times 5$ だけ増加してしまうため、代わりに $F$ に $-A\times 5$ を加算しておきます。

実際に平行移動を行うと、以下の画像のようになります。

線形計画法の解法として、「端の点を試す」という手法がありますが、今回もそれは有効です。まず、$x$ 座標が負の点を考える必要をなくすために、$x$ 座標が $-1$ である場合を試します。
$x$ 座標が $-1$ であるような青い点は複数存在する可能性がありますが、$A,E>0$ より、そのような点のうち、$y$ 座標が最も大きい点のみを試せば十分であることが分かります。したがって、試すべき点は上の図では $(-1,7)$ となります。

以上より、この問題は$0\le x$ の範囲で考えられるようになりました。

帰着後の問題を高速に解く

上記の様々な議論により、考えるべき格子点はfloor sumの時と同様に三角形領域$(\{(x,y)|0\le x,0\le y,Bx+Cy\le D\})$の内部及びその境界上に限定することができました。
そしてこの問題も、floor sumの時と同様に、境界線を繰り返しせん断変形することで高速に解くことができます。

もう一度今から解く必要のある問題を書いておきます。

制約...$A,B,C,E>0$
点 $(x,y)$ が $(\lfloor \frac{D-Ci}{B}\rfloor ,i)\{0\le \lfloor \frac{D-Ci}{B}\rfloor ,i=0,1,2,...\}$ にのみ存在しうるとき、$Ax+Ey+F$ の最大値を求めよ。

これを解くためにこのような再帰関数「 $\text{solve}(A,B,C,D,E,F)$ 」を定義します。
指示がない限り、$1,2,3,...$ のように番号順に実行されます。

$\text{solve}(A,B,C,D,E,F)$ を以下のように定義する。

1. もし、$D<0$ ならば、$-\infty$ を返し、関数を終了する。
2. もし、$C\le 0$ ならば、$-\infty$ を返し、関数を終了する。
3. もし、$E>0$ ならば、4.へ、そうでなければ6.へ
4. もし、$B>C$ ならば、$B$ と $C$ を入れ替え、$A$ と $E$ も入れ替える。
5. 左端での値 $A\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +E\lfloor \frac{D}{C}\rfloor +F$ と右端での値 $A\lfloor \frac{D}{B}\rfloor +F$ と $\text{solve}(A,B,C-B\lfloor \frac{C}{B}\rfloor ,D-B(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1),E-A\lfloor \frac{C}{B}\rfloor ,F+A(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1))$ の中で最も大きい値を返し、関数を終了する。
6. 右端での値 $A\lfloor \frac{D}{B}\rfloor +F$ を返し、関数を終了する。

これだけだとよく分からない(特に5.)ので、図を用いて説明していきます。

1について

$D<0$ のとき、そもそも考慮すべき点が存在しないため、最大値は存在しません。そのため $-\infty$ を返します。

2について

$C\le 0$ であるということは、直前の関数内では $C$ が $B$ の倍数であったことになります。このときは、存在しうる点 $(x,y)$ はすべてが一直線上に並ぶため、左端または右端での値が最大となります。したがって、$C\le 0$ の時は、この最大値に影響しないように $-\infty$ を返すようにします。

3,6について

まず、常に $A>0$ が保証されます。

$E\le 0$ のとき、$Ax+Ey+F$ を最大化するためには $x$ をできるだけ大きく、$y$ をできるだけ小さくしたいため、領域内の右端かつ下端である点 $(\lfloor \frac{D}{B}\rfloor ,0)$ を試すのが最適です。そのため、6に行きます。

4について

もし領域が縦長 $(B>C)$ であるなら、$B,C$ を入れ替え、$A,E$ も忘れずに入れ替えて、領域を横長にします。

5について

先ほどの図をもう一度載せます。$(B=3,C=16,D=109)$
両端の点は紫色のバツ印にしてあります。

右端の点は直感的な右端で問題ありませんが、左端は必ずしも $y$ 軸上であるとは限りません。より厳密には、右端の点は $y$ 座標が最小の $0$ の $(\lfloor \frac{D}{B}\rfloor ,0)$ であり、左端の点は $y$ 座標が最大の $\lfloor \frac{D}{C}\rfloor$ の $(\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor ,\lfloor \frac{D}{C}\rfloor )$ になります。

まずはこの両端の点についてを試します。左端での値は $A\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +E\lfloor \frac{D}{C}\rfloor +F$ で、右端での値は $A\lfloor \frac{D}{B}\rfloor +F$ であるので、この $2$ つの値が最大値候補になります。
そのあと、floor sumと同じように $(x\mapsto x-\lfloor \frac{C}{B}\rfloor (y-\lfloor \frac{D}{C}\rfloor ),y\mapsto y)$ とせん断変形をし、$x$ 軸正方向に $-(\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ だけ平行移動します。平行移動後は、上図での左端の点は $(-1,\lfloor \frac{D}{C}\rfloor )$ に移ります。以下にその図を載せておきます。(移動前の点と線は薄く表示しています。)

このせん断変形と平行移動により、直線 $Bx+Cy=D$ の方程式は $Bx+(C-B\lfloor \frac{C}{B}\rfloor )y=D-B(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ になり、最大化対象の式である $Ax+Ey+F$ も$A(x-\lfloor \frac{C}{B}\rfloor (y-\lfloor \frac{D}{C}\rfloor )+\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)+Ey+F=Ax+(E-A\lfloor \frac{C}{B}\rfloor )y+F+A(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ になります。 これが複雑なせいで次に呼ばれる $\text{solve}$ 関数の中身も複雑になっています。

移動後の図に着目すると、$x$ 座標が $-1$ の点が複数ありますが、試す必要があるものは結局 $y$ 座標が最大のものになります。しかし、その点は左端の点であったものであり、すでに候補にあがっているので試す必要はないです。以上より、$x$ 座標が負の点は考える必要がなくなりました。
したがって、最初と同じ状況が生じるため、今の状況に対して $\text{solve}$ 関数を呼び、その返り値と端の値を比べてより大きい方を返すことで再帰的にこの問題を解くことができます。
なお、次に呼ぶべき関数の各引数 $A,B,C,D,E,F$ はそれぞれ $A,B,C-B\lfloor \frac{C}{B}\rfloor ,D-B(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1),E-A\lfloor \frac{C}{B}\rfloor ,F+A(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ になります。

計算量解析

$\text{solve}$ 関数の第 $2$ 引数と第 $3$ 引数に着目すると、floor sumのときと同様にして時間計算量が $O(\log B)$ であることが分かります。

実装について

前処理で $A,B,C,E>0$ としたあと、ステップ $1$ ～ $6$ をそのまま再帰関数として実装すればいいです。実装例はこのブログの上部にあります。

最後に

紹介したアルゴリズムで殴れる問題をいくつか紹介しておきます。
ただし、floor sumは有名すぎるので、主に $2$ つ目になります。

https://judge.yosupo.jp/problem/min_of_mod_of_linear
$\underset{0\le i<N}{\min }(Ai+B)\mathrm{mod}M=\underset{0\le i\le N-1}{\max }-((Ai+B)\mathrm{mod}M)=\underset{0\le i\le N-1}{\max }-(Ai+B-M\lfloor \frac{Ai+B}{M}\rfloor )=\underset{0\le i\le N-1}{\max }(M\lfloor \frac{Ai+B}{M}\rfloor -Ai-B)$ であるので、上部で紹介したコードの中の floor_max 関数をコピペするだけで解けます。

https://atcoder.jp/contests/arc139/tasks/arc139_b
$A$ 加算と $B$ 加算をそれぞれ $x$ 回, $y$ 回使うとすると、格子点限定の線形計画法の問題になり、これは $2$ つ目の説明中に出てきたものとほぼ同じようにして解けます。
ちなみに、この問題を解いたことでこのブログを書くことを決めました。
なお、C++で実装したところ、実質fastestを取ることができました。

明日の新歓ブログリレー2026の担当は @Water_Castle, @2251799813685248 です。