問題一覧 > 通常問題

No.3397 Max Weighted Floor of Linear

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : 👑 Mizar / テスター : amentorimaru seekworser cleantted
ProblemId : 12833 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-12-05 18:33:48
コンテストの他の問題:
想定実行時間
Fastest解: ~0.100秒, Writer想定解(C++): 0.200~0.300秒, Writer想定解(PyPy3): 0.500~0.900秒

問題文

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

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

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

つまり、整数 $x$ を $0$ 以上 $N$ 未満で動かしたとき、式 $Ax+B\left\lfloor(Cx+D)/M\right\rfloor$ が取りうる値の中で最大のものを求めてください。

$\lfloor\cdot\rfloor$ は床関数（実数に対して自身以下の最大の整数を返す関数）を示します。

入力

$T$
$N _ 1$ $M _ 1$ $A _ 1$ $B _ 1$ $C _ 1$ $D _ 1$
$N _ 2$ $M _ 2$ $A _ 2$ $B _ 2$ $C _ 2$ $D _ 2$
$\vdots$
$N _ T$ $M _ T$ $A _ T$ $B _ T$ $C _ T$ $D _ T$
  • $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$
  • 入力は全て整数

出力

$T$ 行出力して下さい。

最後に改行してください。

サンプル

サンプル1
入力
8
1 1 0 0 0 0
5 3 7 2 2 1
3 2 -6 7 1 1
4 2 1 -10 1 0
6 3 -8 9 2 2
10 5 -3 10 2 0
12 10 -1 7 4 1
12 4 -18 19 3 3
出力
0
34
1
1
2
6
18
3

$f(x)=Ax+B\left\lfloor(Cx+D)/M\right\rfloor$ とおくと、

  • $N=1, M=1, A=0, B=0, C=0, D=0$ のとき、 $f(x)$ は $0\leq x\lt N$ において $\lbrack 0\rbrack$ となり、 $x=0$ のときに最大値 $f(0)=0$ を取ります。
  • $N=5, M=3, A=7, B=2, C=2, D=1$ のとき、 $f(x)$ は $0\leq x\lt N$ において $\lbrack 0, 9, 16, 25, 34\rbrack$ となり、 $x=4$ のときに最大値 $f(4)=34$ を取ります。
  • $N=3, M=2, A=-6, B=7, C=1, D=1$ のとき、 $f(x)$ は $0\leq x\lt N$ において $\lbrack 0, 1, -5\rbrack$ となり、 $x=1$ のときに最大値 $f(1)=1$ を取ります。
  • $N=4, M=2, A=1, B=-10, C=1, D=0$ のとき、 $f(x)$ は $0\leq x\lt N$ において $\lbrack 0, 1, -8, -7\rbrack$ となり、 $x=1$ のときに最大値 $f(1)=1$ を取ります。
サンプル2
入力
10
65536 52220 7325 -20393 18757 11822
65536 47257 -20148 27317 34855 9762
65536 58215 -20112 35971 32549 36876
65536 57269 -19804 32041 35397 53181
65536 60607 14512 -37473 23471 16441
65536 57995 26034 -33647 44873 14564
65536 56689 -24409 39848 34725 14205
65536 50405 22027 -35447 31322 8
65536 25573 11413 -18490 15785 7935
65536 53895 19237 -33308 31127 29265
出力
15775
5642
22785
29754
27308
25196
9985
35441
12752
15221

サンプル3
入力
10
1000000000 102334155 433494437 -701408733 63245986 31415926
1000000000 102334155 -433494437 701408733 63245986 31415926
1000000000 484213958 185444158 -300051715 299263911 32091580
1000000000 771251471 185127374 -485073613 294346581 538843377
1000000000 679842423 -216301801 395451124 371856676 421561913
1000000000 687384999 -262204151 424255264 424827257 346851418
1000000000 432108097 -119358786 164913823 312744541 344218736
1000000000 779304889 -280890788 483327461 452901153 335911945
1000000000 452352635 109686923 -286225731 173349784 301388694
1000000000 971385323 370977589 -600253428 600350066 12805751
出力
486080765
215327987
280165601
146171564
245214372
214077322
131370897
208333696
95522302
592340299

  • $f(x) = 433494437 x - 701408733 \lfloor (63245986 x + 31415926) / 102334155 \rfloor$

  • $f(x) = -433494437 x + 701408733 \lfloor (63245986 x + 31415926) / 102334155 \rfloor$

（日本語問題文版）

(English statement version)

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。