問題一覧 > 通常問題

No.3398 Accuracy of Integer Division Approximate Function 2

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : Mizar / テスター : 👑 seekworser 👑 amentorimaru cleantted
お気に入りにしたユーザー ProblemId : 12369 / 自分の提出
問題文最終更新日: 2026-04-21 10:30:15
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 (順位表) の他の問題:
Note
For this problem, using arbitrary-precision integers is recommended.
Expected Execution Time
Fastest solution: ~0.050 sec, Writer's intended solution (PyPy3): 0.100~0.300 sec

Previous problem in the series: No.2440 Accuracy of Integer Division Approximate Functions

Story
You do not necessarily need to read this story to solve the problem.
(Click here to expand or collapse)

Mizar wanted to quickly compute $\lfloor x/10^{19}\rfloor$ for the range $0\leq x\lt 2^{128}$.

Instead of performing floor division by $10^{19}$, Mizar examined the error of an approximate function that performs floor division by $2^{64}$, then multiplies by $\lfloor 2^{128}/10^{19}\rfloor$, and finally performs floor division by $2^{64}$.

That is, letting $D=10^{19},A=2^{64},B=2^{64}$, Mizar considered the error function $\Delta$ defined as follows for a non-negative integer $x$.

  • $\Delta(D,A,B,x) := \left\lfloor\dfrac{x}{D}\right\rfloor-\left\lfloor\left\lfloor\dfrac{x}{A}\right\rfloor\cdot\dfrac{\lfloor AB/D\rfloor}{B}\right\rfloor$
  • $\Delta(10^{19},2^{64},2^{64},x) = \left\lfloor\dfrac{x}{10^{19}}\right\rfloor-\left\lfloor\left\lfloor\dfrac{x}{2^{64}}\right\rfloor\cdot\dfrac{34028236692093846346}{2^{64}} \right\rfloor$
  • $\lfloor 2^{128}/10^{19}\rfloor = 34028236692093846346$

Evaluating the error function $\Delta$ for $D=10^{19},A=2^{64},B=2^{64}$ gives the following.

  • When $0\leq x\lt 156624322790854844120000000000000000000$, $0\leq\Delta\leq 2$ is guaranteed.
  • When $x = 156624322790854844120000000000000000000$, $\Delta=3$.
  • When $0\leq x\lt 1164985662416622730250000000000000000000$, $0\leq\Delta\leq 3$ is guaranteed.
  • When $x = 1164985662416622730250000000000000000000$, $\Delta=4$.
  • Since $2^{128}\lt 1164985662416622730250000000000000000000$, $0\leq\Delta\leq 3$ is guaranteed in the range $0\le x<2^{128}$.

Mizar became interested in the problem of finding the smallest $x$ such that the error $\Delta$ exceeds a non-negative integer $K$, and defined this problem as follows.

(Note that $D=10^{19},A=2^{64},B=2^{64}$ is outside the input constraints of this problem.)

Problem Statement

There are $T$ test cases.

For each test case, you are given positive integers $D,A,B$ and a non-negative integer $K$.

Define the functions $\Delta(D,A,B,x)$ and $x_{\min}(D,A,B,K)$ as follows.

  • $\Delta(D,A,B,x) := \left\lfloor\dfrac{x}{D}\right\rfloor-\left\lfloor\left\lfloor\dfrac{x}{A}\right\rfloor\cdot\dfrac{\lfloor AB/D\rfloor}{B}\right\rfloor$
  • $x_{\min}(D,A,B,K) := \min\lbrace x\in\mathbb{Z}_{\ge 0}\mid K \lt \Delta(D,A,B,x) \rbrace$
  • $\mathbb{Z}_{\ge 0}$ denotes the set of all non-negative integers, including $0$.
  • $\lfloor \cdot \rfloor$ denotes the floor function.

If there exists a non-negative integer $x$ satisfying $K \lt \Delta(D,A,B,x)$, output $x_{\min}(D,A,B,K)$, that is, the smallest non-negative integer $x$ satisfying $K \lt \Delta(D,A,B,x)$.

If there is no non-negative integer $x$ satisfying $K \lt \Delta(D,A,B,x)$, output $-1$.

The value to be output may exceed the range representable by a 64-bit integer.

Input

$T$
$D _ 1\ A _ 1\ B _ 1\ K _ 1$
$D _ 2\ A _ 2\ B _ 2\ K _ 2$
$\vdots$
$D _ T\ A _ T\ B _ T\ K _ T$
  • $1 \leq T \leq 100$
  • $1 \leq D \leq 10^{18}$
  • $1 \leq A \leq 10^{18}$
  • $1 \leq B \leq 10^{18}$
  • $0 \leq K \leq 64$
  • All inputs are integers.

Output

Output $T$ lines.

On the $i$-th line, output the answer to the $i$-th test case. $(1\le i\le T)$

The value to be output may exceed the range representable by a 64-bit integer.

Print a newline at the end.

Sample

Sample 1
Input
2
1 1 1 0
998244353 1000000000 1000000000 2
Output
-1
1391680038999995155
  • In the first test case, $D=1,A=1,B=1,K=0$.

    • $\Delta(1,1,1,x) := \lfloor x/1\rfloor - \lfloor \lfloor x/1 \rfloor \cdot 1/1 \rfloor = \lfloor x\rfloor - \lfloor x\rfloor = 0$
    • Thus, $\Delta(1,1,1,x) = 0$.
    • Therefore, no $x$ satisfies $K=0 \lt \Delta(1,1,1,x)$, and the answer is $-1$.
  • In the second test case, $D=998244353,A=10^{9},B=10^{9},K=2$.

    • $\Delta(998244353,10^{9},10^{9},x) := \lfloor x/998244353 \rfloor - \lfloor \lfloor x/10^{9} \rfloor \cdot 1001758734/10^{9} \rfloor$
    • $\lfloor 10^{9}\cdot 10^{9}/998244353 \rfloor = 1001758734$
    • When $0 \leq x \lt 1391680038999995155$, $\Delta(998244353,10^{9},10^{9},x) \leq 2$.
    • Also, $\Delta(998244353,10^{9},10^{9},1391680038999995155) = 1394127635 - 1394127632 = 3$.
    • Thus, $x_{\min}(998244353,10^{9},10^{9},2) = 1391680038999995155$.

Sample 2
Input
15
6 4 5 0
6 4 5 1
6 4 5 2
6 4 9 0
6 4 9 1
8 12 4 0
10 3 2 0
10 3 2 1
10 3 2 4
5 3 1 0
5 3 1 2
12 18 25 2
20 30 7 4
15 25 9 3
15 25 10 3
Output
6
54
114
6
-1
8
10
20
50
5
15
948
1340
-1
720

Sample 3
Input
20
1000000 64000000 1234567 3
1000000 64000000 987654321 7
1048576 33554432 1000003 0
1048576 33554432 123 5
536870912 16384 16384 2
536870912 32768 8192 4
786432 1310720 6000000 6
786432 1310720 6000001 6
4194304 67108864 1024 9
4194304 67108864 1025 9
3145728 5242880 1 8
7340032 5242880 11 1
1045430272 134217728 1073741232 9
1030750208 201326592 1073740858 8
1024458752 167772160 1073740873 9
1018167296 234881024 1073741497 7
1013972992 268435456 1073741362 9
420196140727489673 679891637638612258 999999999999999989 7
999999999999999999 999999999999999998 999999999999999989 7
1000000000000000000 999999999999999999 999999999999999999 7
Output
4000000
8000000
1048576
6291456
1610612736
2684354560
-1
55050254155776
41943040
41943040
66060288
51380224
1274842250977276329984
1658692265100711034880
1555361789906621825024
1657972676523719655424
2434969170292362969088
9007968880765895055838800035237338317
599999999999999992200000000000000015199999999999999992
5999999999999999991000000000000000002000000000000000000

The value to be output may exceed the range representable by a 64-bit integer.

(Japanese statement version)

(English statement version)

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