問題一覧 > 通常問題

No.3397 Max Weighted Floor of Linear

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 27
作問者 : Mizar / テスター : 👑 amentorimaru 👑 seekworser cleantted
お気に入りにしたユーザー ProblemId : 12833 / 自分の提出
問題文最終更新日: 2026-04-21 10:30:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:
Expected Execution Time
Fastest solution: ~0.100 s, Writer's solution (C++): 0.200~0.300 s, Writer's solution (PyPy3): 0.500~0.900 s

Problem Statement

There are $T$ test cases.

For each test case, you are given positive integers $N,M$ and integers $A,B,C,D$.

Find $\max\left\lbrace Ax+B\left\lfloor(Cx+D)/M\right\rfloor\mid x\in\mathbb{Z},\ 0\leq x\lt N\right\rbrace$.

In other words, find the maximum value that the expression $Ax+B\left\lfloor(Cx+D)/M\right\rfloor$ can take as the integer $x$ ranges over values at least $0$ and less than $N$.

$\lfloor\cdot\rfloor$ denotes the floor function (the function that returns, for a real number, the largest integer not exceeding it).

Input

$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$
  • All input values are integers.

Output

Print $T$ lines.

Print a newline at the end.

Sample

Sample 1
Input
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
Output
0
34
1
1
2
6
18
3

Let $f(x)=Ax+B\left\lfloor(Cx+D)/M\right\rfloor$.

  • When $N=1, M=1, A=0, B=0, C=0, D=0$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0\rbrack$, and the maximum value $f(0)=0$ is attained at $x=0$.
  • When $N=5, M=3, A=7, B=2, C=2, D=1$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0, 9, 16, 25, 34\rbrack$, and the maximum value $f(4)=34$ is attained at $x=4$.
  • When $N=3, M=2, A=-6, B=7, C=1, D=1$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0, 1, -5\rbrack$, and the maximum value $f(1)=1$ is attained at $x=1$.
  • When $N=4, M=2, A=1, B=-10, C=1, D=0$, $f(x)$ over $0\leq x\lt N$ is $\lbrack 0, 1, -8, -7\rbrack$, and the maximum value $f(1)=1$ is attained at $x=1$.
Sample 2
Input
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
Output
15775
5642
22785
29754
27308
25196
9985
35441
12752
15221

Sample 3
Input
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
Output
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$

(Japanese statement version)

(English statement version)

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