\(x\) を正整数，\(y\) を非負整数として \(Ax-By=N\), \(Bx-Ay=N\) という作り方があります．\(N\) に関する制約より正整数 \(x,y\) に対する \(Ax+By\) という作り方は考慮する必要がありません．なので，\(x\) が最小正であるような解をとれば自動的に \(y\) は非負になったりします．

（これによって場合分けがいくらか減るものの，本解説の解法自体は \(N\) の上限制約がなくても適用できると思います）．

それぞれの最小解は \((x,y)\) から \((A-y,B-x)\) という要領で変換できて，\(2\) 種の最小解のコスト和は定数です．

\(2\) 種それぞれ計算することにして，だいたい次が出来ればよいです：以下の不等式をすべて満たす格子点 \((x,y)\) についての \(Xx+Yy\) の総和を計算してください．

• \(1\leq x \leq B\)
• \(1\leq Ax-By\leq N\)
• \(Xx+Yy\leq C\)

関連する直線の交点の \(x\) 座標で切り分ければ，定数個の区間について，次のような領域内の格子点に関する計算に帰着されます：\(L\leq x < R\) かつ \(\lfloor(ax+b)/c\rfloor<y\leq \lfloor(dx+e)/f\rfloor\)

上側までの領域から下側までの領域を引くという計算をすれば，\(0\leq y\leq \lfloor (ax+b)/c\rfloor\) での和を求めることになり，結局次のような問題定数個に帰着されます．

\(L,R,a,b,c,i,j\) が与えられるので，\(\sum_{L\leq x<R}x^i \lfloor(ax+b)/c\rfloor^j\) を求めよ．

\(i=0,j=1\) の場合がとても有名ですが，この問題も解けることが知られています．

• \(i=0,j=1\) verify 問題：■ ■, ACL実装
• そのまま出題例：■
• floor sum の亜種の出題例：■ ■

上に挙げた問題を統一的に扱う方法をひとつ紹介します．\(y=(ax+b)/c\) という直線を超えないように \((0,0)\) から \((N,\lfloor (ax+b)/c\rfloor)\) まで格子点を \(x\) 方向・\(y\) 方向に移動することを繰り返して到達する経路であって，\(y\) 方向に貪欲に進む経路を考えます．

適当なモノイドを固定してモノイドの元 \(x, y\) をとり，各軸方向の移動のタイミングでこれらのモノイドの元をかけていくと，パスに対するモノイドの元の総積が定義されます （上に挙げた問題のひとつが この操作の類似を扱っています）．

このような総積を求める問題は，おそらくお好みの \(\sum \lfloor (ax+b)/c\rfloor\) の計算方法と同様の計算を試みると，解くことができると思います．

\(\sum_{L\leq x<R}x^i \lfloor(ax+b)/c\rfloor^j\) の計算に適用するには，各軸方向の移動を

• \(x\) 方向の移動：\(\mathrm{ANS}[i][j]\) に \(x^iy^j\) を加算し，\(x\) をインクリメントする．
• \(y\) 方向の移動：\(y\) をインクリメントする．

となるように適切なモノイドを設計すればよいです．具体的には \(x=y=0\) からはじめた場合の最終的な \((x,y,\mathrm{ANS})\) をデータとすればこれらを結合する演算を記述することができます．

• 解答例：https://atcoder.jp/contests/arc183/submissions/57133237