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