問題一覧 > 通常問題

No.2440 Accuracy of Integer Division Approximate Functions

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : 👑 MizarMizar / テスター : 👑 amentorimaruamentorimaru
0 ProblemId : 10018 / 自分の提出
問題文最終更新日: 2023-08-23 20:59:17

問題文

$Q$ 個のクエリが与えられる。

$i$ 番目のクエリ $(1\leq i\leq Q)$ では、整数 $N_i,D_i,M_i,S_i$ が与えられる。 $1\leq n\leq N_i$ かつ $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$ となるような 整数 $n$ がいくつあるかを数え上げ、 $C_i$ とおく。 この整数 $C_i$ を答えよ。

$\lfloor\cdot\rfloor$ 記号 と $C_i$ の数学的定義と説明（ここをクリックで開閉します）

  • $\lfloor\cdot\rfloor$ 記号の数学的定義と説明

    • "$\lfloor x\rfloor$" は、実数 $x$ に対し、 $x$ を超えない最大の整数を返す関数であり、 $\lfloor x\rfloor=\max\{n\in\mathbb{Z}\mid n\leq x\}$ と定義する。
    • "$\mathbb{Z}$" は、「整数全体の集合」を意味する。
    • "$n\in\mathbb{Z}$" は、「$n$ は 『整数全体の集合』に属する」、つまり「$n$ は整数」を意味する。
    • "$\{n\in\mathbb{Z}\mid n\leq x\}$" は、「$x$ 以下の整数からなる集合」を意味する。
    • "$\max\{n\in\mathbb{Z}\mid n\leq x\}$" は、「『$x$ 以下の整数からなる集合』のうち、最大の要素」、つまり「$x$ を超えない最大の整数」を意味する。

    • "$\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor$" は、「"$\displaystyle\frac{n}{D_i}$" を超えない最大の整数」を意味する。

    • "$\displaystyle\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$" は、「"$\displaystyle\frac{M_i\times n}{2^{S_i}}$" を超えない最大の整数」を意味する。

  • $C_i$ の数学的定義と説明

    • $\displaystyle C_i = \#\left\{n\in\mathbb{Z}\ \middle|\ 1\leq n\leq N_i,\ \left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor\right\}\quad(1\leq i\leq Q)$

    • "$\displaystyle\left\{n\in\mathbb{Z}\ \middle|\ 1\leq n\leq N_i,\ \left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor\right\}$" は、 "$1\leq n\leq N_i$ かつ、 $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$" であるような "整数 $n$" の集合を意味する。

    • "$\displaystyle\#\left\{n\in\mathbb{Z}\ \middle|\ 1\leq n\leq N_i,\ \left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor\right\}$" は、 "$1\leq n\leq N_i$ かつ、 $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$" であるような "整数 $n$" の集合の要素数を意味する。

    • 有限集合 $A$ の要素数は $n(A)$ や $|A|$ のように表記する方法もあるが、 $n$ の文字や $|$ の記号が重複するため、ここでは $\#A$ のような表記を用いている。

入力

$Q$
$N_1\ D_1\ M_1\ S_1$
$N_2\ D_2\ M_2\ S_2$
$N_3\ D_3\ M_3\ S_3$
$\ \,\vdots$
$N_Q\ D_Q\ M_Q\ S_Q$

  • $1\leq Q\leq 10000$
  • $N_i = 10^{18}\quad(1\leq i\leq Q)$
  • $1\leq D_i\leq 10^{18}\quad(1\leq i\leq Q)$
  • $0\leq M_i\leq 10^{18}\quad(1\leq i\leq Q)$
  • $0\leq S_i\leq 120\quad(1\leq i\leq Q)$
  • 入力はすべて整数

出力

$C_1$
$C_2$
$C_3$
$\ \,\vdots$
$C_Q$

$Q$ 行出力せよ。 $i\ (1\leq i\leq Q)$ 行目 には、 $1\leq n\leq N_i$ かつ $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$ となるような 整数 $n$ がいくつあるかを数え上げた整数 $C_i$ を出力せよ。

サンプル

サンプル1
入力
7
1000000000000000000 1 1 0
1000000000000000000 1 0 120
1000000000000000000 3 1 1
1000000000000000000 3 1 2
1000000000000000000 47 196241958230952677 63
1000000000000000000 998244353 155014655926305585 87
1000000000000000000 1000000007 618970015309900031 89
出力
1000000000000000000
0
2
5
996563582276314846
1000000000000000000
999999999859993400

$n$ が 整数 かつ $1\leq n\leq 10^{18}$ において、

  • $\displaystyle\left\lfloor\frac{n}{1}\right\rfloor=\left\lfloor\frac{1\times n}{2^{0}}\right\rfloor$ は成り立ちます。 $(C_1=1000000000000000000)$

  • $\displaystyle\left\lfloor\frac{n}{1}\right\rfloor=\left\lfloor\frac{0\times n}{2^{120}}\right\rfloor$ は成り立ちません。 $(C_2=0)$

  • $\displaystyle\left\lfloor\frac{n}{3}\right\rfloor=\left\lfloor\frac{1\times n}{2^{1}}\right\rfloor$ が成り立つのは $n\in\{1,3\}$ の時のみです。 $(C_3=2)$

  • $\displaystyle\left\lfloor\frac{n}{3}\right\rfloor=\left\lfloor\frac{1\times n}{2^{2}}\right\rfloor$ が成り立つのは $n\in\{1,2,4,5,8\}$ の時のみです。 $(C_4=5)$

  • $\displaystyle\left\lfloor\frac{n}{47}\right\rfloor=\left\lfloor\frac{196241958230952677 \times n}{2^{63}}\right\rfloor$ は必ずしも成り立ちません。 $(C_5=996563582276314846)$

    • 例えば、 $\displaystyle\left\lfloor\frac{10^{18}-4}{47}\right\rfloor=21276595744680850,\ \left\lfloor\frac{196241958230952677 \times (10^{18}-4)}{2^{63}}\right\rfloor=21276595744680851$ なので、 $n=10^{18}-4=999999999999999996$ の時は $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$ が成り立ちません。

  • $\displaystyle\left\lfloor\frac{n}{998244353}\right\rfloor=\left\lfloor\frac{155014655926305585 \times n}{2^{87}}\right\rfloor$ は成り立ちます。 $(C_6=1000000000000000000)$

  • $\displaystyle\left\lfloor\frac{n}{1000000007}\right\rfloor=\left\lfloor\frac{618970015309900031 \times n}{2^{89}}\right\rfloor$ は必ずしも成り立ちません。 $(C_7=999999999859993400)$

    • 例えば、 $\displaystyle\left\lfloor\frac{10^{18}-50}{1000000007}\right\rfloor=999999992,\ \left\lfloor\frac{618970015309900031 \times (10^{18}-50)}{2^{89}}\right\rfloor=999999993$ なので、 $n=10^{18}-50=999999999999999950$ の時は $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$ が成り立ちません。

オーバーフローに注意してください。

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