問題一覧 > 通常問題

No.2440 Accuracy of Integer Division Approximate Functions

レベル : / AI推定難易度 : 2550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : Mizar / テスター : 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 10018 / 自分の提出
問題文最終更新日: 2023-08-23 20:59:17
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

Problem Statement

You are given $Q$ queries.

In the $i$-th query $(1\leq i\leq Q)$, you are given integers $N_i,D_i,M_i,S_i$. Let $C_i$ be the number of integers $n$ such that $1\leq n\leq N_i$ and $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$. Find this integer $C_i$.

Mathematical definitions and explanations of the $\lfloor\cdot\rfloor$ symbol and $C_i$ (click here to expand/collapse)
  • Mathematical definition and explanation of the $\lfloor\cdot\rfloor$ symbol

    • "$\lfloor x\rfloor$" is a function that, for a real number $x$, returns the largest integer not exceeding $x$, and is defined as $\lfloor x\rfloor=\max\{n\in\mathbb{Z}\mid n\leq x\}$.
    • "$\mathbb{Z}$" means "the set of all integers".
    • "$n\in\mathbb{Z}$" means "$n$ belongs to 'the set of all integers'", that is, "$n$ is an integer".
    • "$\{n\in\mathbb{Z}\mid n\leq x\}$" means "the set consisting of the integers less than or equal to $x$".
    • "$\max\{n\in\mathbb{Z}\mid n\leq x\}$" means "the largest element of 'the set consisting of the integers less than or equal to $x$'", that is, "the largest integer not exceeding $x$".
    • "$\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor$" means "the largest integer not exceeding "$\displaystyle\frac{n}{D_i}$"".

    • "$\displaystyle\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$" means "the largest integer not exceeding "$\displaystyle\frac{M_i\times n}{2^{S_i}}$"".

  • Mathematical definition and explanation of $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\}$" means the set of "integers $n$" such that "$1\leq n\leq N_i$ and $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$".

    • "$\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\}$" means the number of elements in the set of "integers $n$" such that "$1\leq n\leq N_i$ and $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$".

    • The number of elements of a finite set $A$ can also be written as $n(A)$ or $|A|$, but since the letter $n$ and the symbol $|$ would be duplicated, the notation $\#A$ is used here.

Input

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

Output

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

Output $Q$ lines. On line $i\ (1\leq i\leq Q)$, output the integer $C_i$, the number of integers $n$ such that $1\leq n\leq N_i$ and $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$.

Sample

Sample 1
Input
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
Output
1000000000000000000
0
2
5
996563582276314846
1000000000000000000
999999999859993400

For $n$ an integer with $1\leq n\leq 10^{18}$:

  • $\displaystyle\left\lfloor\frac{n}{1}\right\rfloor=\left\lfloor\frac{1\times n}{2^{0}}\right\rfloor$ holds. $(C_1=1000000000000000000)$

  • $\displaystyle\left\lfloor\frac{n}{1}\right\rfloor=\left\lfloor\frac{0\times n}{2^{120}}\right\rfloor$ does not hold. $(C_2=0)$

  • $\displaystyle\left\lfloor\frac{n}{3}\right\rfloor=\left\lfloor\frac{1\times n}{2^{1}}\right\rfloor$ holds only when $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$ holds only when $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$ does not always hold. $(C_5=996563582276314846)$

    • For example, $\displaystyle\left\lfloor\frac{10^{18}-4}{47}\right\rfloor=21276595744680850,\ \left\lfloor\frac{196241958230952677 \times (10^{18}-4)}{2^{63}}\right\rfloor=21276595744680851$, so $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$ does not hold when $n=10^{18}-4=999999999999999996$.

  • $\displaystyle\left\lfloor\frac{n}{998244353}\right\rfloor=\left\lfloor\frac{155014655926305585 \times n}{2^{87}}\right\rfloor$ holds. $(C_6=1000000000000000000)$

  • $\displaystyle\left\lfloor\frac{n}{1000000007}\right\rfloor=\left\lfloor\frac{618970015309900031 \times n}{2^{89}}\right\rfloor$ does not always hold. $(C_7=999999999859993400)$

    • For example, $\displaystyle\left\lfloor\frac{10^{18}-50}{1000000007}\right\rfloor=999999992,\ \left\lfloor\frac{618970015309900031 \times (10^{18}-50)}{2^{89}}\right\rfloor=999999993$, so $\displaystyle\left\lfloor\frac{n}{D_i}\right\rfloor=\left\lfloor\frac{M_i\times n}{2^{S_i}}\right\rfloor$ does not hold when $n=10^{18}-50=999999999999999950$.

Be careful of overflow.

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