問題一覧 > 通常問題

No.3398 Accuracy of Integer Division Approximate Function 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 6
作問者 : 👑 Mizar / テスター : seekworser amentorimaru cleantted
ProblemId : 12369 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-12-04 15:46:15
コンテストの他の問題:
注意
この問題では、多倍長整数の使用を推奨します。
想定実行時間
Fastest解: ~0.050秒, Writer想定解(PyPy3): 0.100~0.300秒

前のシリーズ問題: No.2440 Accuracy of Integer Division Approximate Functions

ストーリー
このストーリーは問題を解く上で、必ずしも読む必要はありません。
（ここをクリックすると開閉します）

みざー君は $0\leq x\lt 2^{128}$ の範囲について $\lfloor x/10^{19}\rfloor$ を高速に計算したいと考えました。

みざー君は $10^{19}$ で切り捨て除算をする代わりに、 $2^{64}$ で切り捨て除算し、次に $\lfloor 2^{128}/10^{19}\rfloor$ で乗算し、 最後に $2^{64}$ で切り捨て除算する近似関数の誤差を検討しました。

すなわち、 $D=10^{19},A=2^{64},B=2^{64}$ として、 非負整数 $x$ に対して次のように定義される誤差関数 $\Delta$ を考えました。

  • $\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$

$D=10^{19},A=2^{64},B=2^{64}$ における誤差関数 $\Delta$ を評価すると、

  • $0\leq x\lt 156624322790854844120000000000000000000$ のとき、 $0\leq\Delta\leq 2$ が保証されます。
  • $x = 156624322790854844120000000000000000000$ のとき、 $\Delta=3$ です。
  • $0\leq x\lt 1164985662416622730250000000000000000000$ のとき、 $0\leq\Delta\leq 3$ が保証されます。
  • $x = 1164985662416622730250000000000000000000$ のとき、 $\Delta=4$ です。
  • $2^{128}\lt 1164985662416622730250000000000000000000$ なので、 $0\le x<2^{128}$ の範囲では $0\leq\Delta\leq 3$ が保証されます。

みざー君は、誤差 $\Delta$ が 非負整数 $K$ を超えるような最小の $x$ を求める問題に興味を持ち、この問題を次のように定義しました。

（ $D=10^{19},A=2^{64},B=2^{64}$ は今回の問題では入力制約の範囲外です ）

問題文

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

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

次に示す関数 $\Delta(D,A,B,x)$ と $x_{\min}(D,A,B,K)$ を定義します。

  • $\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}$ は $0$ を含む非負整数全体の集合を表します。
  • $\lfloor \cdot \rfloor$ は床関数を表します。

$K \lt \Delta(D,A,B,x)$ を満たす非負整数 $x$ が存在する場合は $x_{\min}(D,A,B,K)$ 、つまり、 $K \lt \Delta(D,A,B,x)$ を満たす最小の非負整数 $x$ を答えてください。

$K \lt \Delta(D,A,B,x)$ を満たす非負整数 $x$ が存在しない場合は、 $-1$ を答えてください。

出力すべき値は、 64bit 整数で表記できる範囲を超えることがあります。

入力

$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$
  • 入力はすべて整数

出力

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

$i$ 行目には、 $i$ 番目のテストケースの答えを出力して下さい。 $(1\le i\le T)$

出力すべき値は、 64bit 整数で表記できる範囲を超えることがあります。

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

サンプル

サンプル1
入力
2
1 1 1 0
998244353 1000000000 1000000000 2
出力
-1
1391680038999995155

  • 1つ目のテストケースでは、 $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$
    • よって、 $\Delta(1,1,1,x) = 0$ です。
    • したがって、 $K=0 \lt \Delta(1,1,1,x)$ を満たす $x$ は存在せず、答えは $-1$ です。

  • 2つ目のテストケースでは、 $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$
    • $0 \leq x \lt 1391680038999995155$ のとき、 $\Delta(998244353,10^{9},10^{9},x) \leq 2$ です。
    • また、 $\Delta(998244353,10^{9},10^{9},1391680038999995155) = 1394127635 - 1394127632 = 3$ です。
    • よって、 $x_{\min}(998244353,10^{9},10^{9},2) = 1391680038999995155$ です。

サンプル2
入力
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
出力
6
54
114
6
-1
8
10
20
50
5
15
948
1340
-1
720

サンプル3
入力
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
出力
4000000
8000000
1048576
6291456
1610612736
2684354560
-1
55050254155776
41943040
41943040
66060288
51380224
1274842250977276329984
1658692265100711034880
1555361789906621825024
1657972676523719655424
2434969170292362969088
9007968880765895055838800035237338317
599999999999999992200000000000000015199999999999999992
5999999999999999991000000000000000002000000000000000000

出力すべき値は、 64bit 整数で表記できる範囲を超えることがあります。

（日本語問題文版）

(English statement version)

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