No.3398 Accuracy of Integer Division Approximate Function 2
タグ : / 解いたユーザー数 7
作問者 :
amentorimaru
cleantted
Previous problem in the series: No.2440 Accuracy of Integer Division Approximate Functions
(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もしくは右上の雲マークをクリックしてアカウントを作成してください。